题意：给出n个数代表男生 m个数代表女生
要求每个男生给所有女生几个糖果（可以是0个）
每个男生给各个女生糖果的最小值(不是总和） 大于等于男生代表的值
给每个女生的糖果小于等于女生的值 且每个女生至少收到一份足够多的糖果（代表她的值的糖果数量）
ps：男生给各个女生的糖果数量也至少有一个==其男生值
贪心:
显然 男生值小的给女生值大的 是比较亏的 损失值为差值 所以要安排男生值大的给女生值大的 按照男生值大的遍历下来即可 要注意得留一个补自己的值
比赛的时候几乎写出来了 但是数组没有开longlong
数据范围为1e8 但是乘的过程中爆int了
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 const int N=400000+5; ll a[N],b[N]; int main() { int n,m;RII(n,m); rep(i,1,n)scanf("%lld",&a[i]); rep(i,1,m)scanf("%lld",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+m); if(a[n]>b[1]) printf("-1"); else { ll sum=0; int R=m; repp(i,n,1) { if(R==0) { sum+=a[i]*m;continue; } int t=m-1; while(t&&R>=1) { sum+=b[R]; R--;t--; } if(t==0) { sum+=a[i]; if(a[i]==b[R])R--; continue; } else if(t) { t++; while(t--) sum+=a[i]; } } cout<<sum; } return 0; }
其实仔细观察发现 从男生最大值开始遍历 要么一遍遍历结束(如果男生最大值==女生最小值） 要么男生遍历m-1个 剩下一个最小的男士次小值遍历即可！！！
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 用了这个 在下面用scanf就wa了！！！！！ 我还是老老实实用scanf好了
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 const int N=400000+5; ll maxx=0,maxx2=0,minn=(int)1e9; ll sumboy=0,sumgirl=0; ll x;ll ans=0; int n,m; int main() { RII(n,m); rep(i,1,n) { scanf("%lld",&x); if(x>=maxx) { maxx2=maxx; maxx=x; } else if(x>maxx2) maxx2=x; sumboy+=x; } rep(i,1,m) { scanf("%lld",&x); if(x<minn)minn=x; sumgirl+=x; } if(maxx>minn) { printf("-1");return 0; } ans = sumboy*(ll)m; ans += sumgirl; ans -= maxx*m; if(maxx!=minn) ans += maxx-maxx2; cout << ans; return 0; }
注意维护第二大数的方法值得学习