题解 | #奖学金#

贪心策略：
第一步：计算已经取得成绩
第二步：计算每门最大可以还可以获得多少分
第三步: 计算还需取得成绩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;
}