贪心策略:
第一步:计算已经取得成绩
第二步:计算每门最大可以还可以获得多少分
第三步: 计算还需取得成绩P
第四步:按照升序排序
第五步:从小往大取 并注意受限条件。
#include<iostream> using namespace std; #include<vector> #include<algorithm> bool com(vector<int>a,vector<int> b){ return a[0]<b[0]; } void WY1(){ int n , r, avg; while(cin>> n>>r>>avg){ vector<vector<int>> nums; long sum =0; for (int i = 0; i <n ; ++i) { int a,b; cin>>a>>b; sum+=a; //已经拿到分数 nums.push_back({b,r-a});// 消耗值: 次数 } long p = avg*n-sum; // 背包容量 // 不完全背包问题 // 贪心策略 sort(nums.begin(),nums.end(),com); long min_w =0; for(auto v : nums){ if(p-v[1]>=0) //大于等于零 取对应的次数为系数否则取p { p=p-v[1]; min_w +=v[1]*v[0]; }else{ if(p-v[1]<0) { if(p>0) { min_w += p*v[0]; p=0; } } } if(p==0) break; } cout<<min_w<<endl; } } int main(){ WY1(); return 0; }