贪心。按照每加仑的单价从小到大排序,这样才能保证花更少的钱买更多的牛奶。然后暴力就可以了。。
#include <iostream> #include <algorithm> #include <string> #include <cstdio> #include <cstring> using namespace std; const int INF = 0x7f7f7f7f; struct T { int p,a; }s[5010]; bool cmp(T x,T y) { return x.p<y.p; } int main() { int n,m,i; scanf("%d%d",&n,&m); for(i=0;i<m;i++) scanf("%d%d",&s[i].p,&s[i].a); sort(s,s+m,cmp); int sum=0; for(i=0;i<m;i++) { if(n-s[i].a<0) { sum+=n*s[i].p; break; } else { n-=s[i].a; sum+=s[i].a*s[i].p; } } printf("%d\n",sum); return 0; }