链家小明达到平均分，耗费多少祝福值啊

贪心算法，一次就能AC

我用的贪心，不过只ac了64%...

#include <stdio.h> #include <algorithm> using std::sort; const int MAXN = 100100; int n, r, avg; struct Subject { int a, b; } subject[MAXN]; typedef long long LL; LL gap; void read() { int a, b; scanf("%d%d%d", &n, &r, &avg); for (int i = 0; i < n; ++i) { scanf("%d%d", &a, &b); gap += a; subject[i].a = a; subject[i].b = b; } gap = (LL)n * avg - gap; } bool lowestCost(const Subject& p, const Subject& q) { return p.b < q.b; } void work() { if (gap <= 0) { puts("0"); return; } LL res = 0; sort(subject, subject + n, lowestCost); for (int i = 0; i < n; ++i) { LL t = r - subject[i].a; if (t < gap) { res += t * subject[i].b; gap -= t; } else { res += gap * subject[i].b; gap = 0; break; } } printf("%lld\n", res); } int main() { read(); work(); return 0; }

#include #include using std::endl; int main() { long long n,r,avg; std::cin>>n>>r>>avg; std::multimap chengji; long long ai,bi; double pre_avg=0; for(long long i=0;i<n;i++) { std::cin>>ai>>bi; chengji.insert(std::pair(bi,ai)); pre_avg+=ai; } long long mubiao=avg*n; // std::cout<<pre_avg<<" "<<mubiao<<endl; long long result=0; for(auto i=chengji.begin();i!=chengji.end()&&pre_avg<=mubiao;i++) { long long chengji2=i->second; long long sub=r-chengji2; if(pre_avg+sub<mubiao) { pre_avg+=sub; result=result+(sub*i->first); //std::cout<<pre_avg<<"\n"; } else while(chengji2<r&&pre_avg<mubiao) { pre_avg++; result+=i->first; } } std::cout<<result<<endl; }

我也是64