问题描述

快毕业了，Barry希望能通过期末的N门考试来顺利毕业。如果他的N门考试平均分能够达到V分，则他能够成功毕业。现在已知每门的分数不能够超过R；他的第i门考试目前得分为Ai，如果想要在这门科目增加一分则需要多写Bi篇论文。Barry想知道，如果想要毕业的话，他最少需要写多少篇论文？

输入格式(exam.in)

第一行三个整数，N, R, V，分别代表考试科目数，每门考试的最高分，需要达到的平均分。

接下来的N行每行两个整数A, B，分别代表这门考试的目前得分与增加一分需要多写的论文数。

输出格式(exam.out)

一个整数，代表他要毕业最少需要写的论文数。

样例输入

5 5 4

3 1

3 2

5 2

4 7

2 5

样例输出

4

数据范围及约束

对于30%的数据，N<=5, R<=3;

对于100%的数据，N<=100,000, R<=1000,000,000, 1<=V<=R

保证答案不超过10^18.

这是一道贪心模拟题。只要不到限制，就一直先写最便宜的论文。注意要开long long

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long longusing namespace std;LL n,r,v,N,now,ans;struct H{ LL b; LL a;}w[100009];bool cmp(H x,H y){ return x.b
           
            now) { p++; if(now+r-w[p].a<=N) now+=r-w[p].a,ans+=w[p].b*(r-w[p].a); else ans+=w[p].b*(N-now),now=N; } printf("%lld",ans); return 0; }