pumaway @ 2022-08-18 13:57:40
这个代码wa了2个,怎么也找不到错,大佬帮忙看看背
// Problem: P1678 烦恼的高考志愿
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1678
// Memory Limit: 125 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;
//#define MAXN 100010
#define rep(i,a,n) for (ll i=a;i<=n;++i)
#define per(i,a,n) for (ll i=n;i>=a;--i)
#define INF 1000000000
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pob pop_back
#define all(x) (x).begin(),(x).end()
#define ent cout<<'\n'
const int N = 100010;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll n, m;
ll s[N],a[N];
int main()
{
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
cin>>m>>n;
for(int i=0;i<m;++i) cin>>s[i];
for(int i=0;i<n;++i)cin>>a[i];
ll res=0;
sort(s,s+m);
sort(a,a+n);
for(int i=0;i<n;++i)
{
if(a[i]<s[0])
{
res+=s[0]-a[i];
continue;
}
else if(a[i]>s[m-1])
{
res+=s[m-1]-a[i];
continue;
}
ll p1=lower_bound(s,s+m,a[i])-s;
if(s[p1]!=a[i])
{
ll p2=p1-1;
if( (s[p1]-a[i]) > (a[i]-s[p2]) )
res += a[i]-s[p2];
else
res+=s[p1]-a[i];
}
}
cout<<res;
return 0;
}
by wanggk @ 2022-08-18 14:19:06
@pumaway
else if(a[i]>s[m-1])
里面应该是res+=a[i]-s[m-1];
差值必须是大的减小的