求解奖学金问题（贪心）

/*问题描述：有n门课（编号为0～n-1），每门课都有考试。为了拿到奖学金，必须满足所有课程平均成绩至少为avg。每门课由平时成绩和考试成绩相加得到，满足为r。现知道每门课平均成绩ai（0<=i<=n-1），若想让这门课多考一分，需要花bi的时间复习。同时，也可能出现复习再多也不会超过满分的分数。为了拿到奖学金，请问至少需要花多少时间？？

输入描述：每个测试用例第一行为整数n(1<=n<=200)，表示课程数，接下来n行，每行两个整数，分别表示一门课的平均成绩ai和bi，最后一行输入满分r和希望到达的平均成绩avg，以输入n==0结束

4

80 5

70 2

90 3

60 1

100 92.5

样例输出：

100

分析：既然选择用贪心，那么就要制定贪心准则。既然给定了avg平均成绩和n，那么我们不难得出拿到奖学金的总分为n*avg，同时每门课的平均成绩也已给出，那么二者之差就是我们需要复习之后提高的分数了。而且这个分数，要用最少的时间来获得。

所以要对bi进行排序。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<vector>
 6 #include<stack>
 7 #include<map>
 8 #include<set>
 9 #include<list>
10 #include<queue>
11 #include<string>
12 #include<algorithm>
13 #include<iomanip>
14 using namespace std;
15 #define max 201
16 int n;
17 struct score
18 {
19     /* data */
20     int ai;
21     int bi;
22     bool operator < (const score & s)const
23     {
24         return  bi < s.bi;//复习时间递增排序
25     }
26 };
27 
28 score a[max];
29 int r;
30 double avg;
31 int effort = 0;
32 
33 void solve()
34 {
35     int sums = (int) n * avg;//需要达到的总分
36     int cursum = 0;
37     for(int i = 0 ; i< n; i ++)//现有课程的总分
38     {
39         cursum += a[i].ai;
40     }
41     sort(a,a + n);
42     for(int j = 0; j< n;j++)//贪心选择
43     {
44         if(cursum >= sums)//分数达到，结束选择
45         {
46             break;
47         }
48     
49         int cur = cursum;
50         cursum += min(sums - cursum ,r - a[j].ai);
51         effort += a[j].bi * min(sums-cur,r - a[j].ai);
52     }
53 }
54 int main()
55 {
56     while(cin>>n && n != 0 )
57     {
58         for(int i = 0;i < n; i++)
59         {
60             cin>>a[i].ai>>a[i].bi;
61         }
62         cin>>r>>avg;
63         solve();
64         cout<<effort<<endl;
65     }
66     return 0;
67 }

  　　for(int j = 0; j< n;j++)//贪心选择
43     {
44         if(cursum >= sums)//分数达到，结束选择
45         {
46             break;
47         }
48     
49         int cur = cursum;
50         cursum += min(sums - cursum ,r - a[j].ai);
51         effort += a[j].bi * min(sums-cur,r - a[j].ai);
52     }

针对这一段，简单说一下，每门课已经按照单位复习时间递增排了序，50行是为了找出 （需要达到的总分与目前总分的差，每门课的满分r与当前平均成绩ai的差）较小的那个，因为从单位复习时间最少的开始复习（同样是总分加一分，当然是时间越少越好）。sums-curcum==70,100-60=40，，所以花费时间为effort+= 1 * 40。即把60的成绩复习到满分，花费40分钟，此时目前总分为340,还需30分，继续循环单位复习时间第二小的那个，是70 ，2。sums-cumin==30,100-70 ==30 ，所以这个复习到满分刚好达到条件。此时（effort += 2 *（30）） == 100.所以最终至少需要花费100单位时间去复习。如果sums-cursum  < r-a[j].ai  ，那就意味着当前课程不需要到满分就能拿奖学金了，最后加上需要的时间就行了