这就是传说中的蘑菇题

题目的大意我就不说了，大家自己去google一下吧，有人说过了

就算锻炼了一下用vector,algorithm吧

算法很简单，先按照来的时间和报酬排序

然后在一个一个的处理，未处理的就加入到suspend里面，等到下一轮处理

有个地方比较特殊，就是为处理的任务，如果他的截止时间在F之前，那么会算惩罚，如果超出了，就不算了

刚开始这个地方没注意，所以贡献了几次WA

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <vector>
  4 using namespace std;
  5 
  6 struct rect
  7 {
  8 public:
  9     rect(int a,int b,int c,int d,int e,int f,int g):m_a(a),m_b(b),m_c(c),m_d(d),m_e(e),m_f(f),m_g(g){}
 10     int m_a,m_b,m_c,m_d,m_e,m_f,m_g;
 11 };
 12 
 13 vector<rect> job,suspend;
 14 vector<rect>::iterator it;
 15 
 16 bool compare(rect a,rect b)
 17 {
 18     if (a.m_c<b.m_c)
 19         return 1;
 20     else if (a.m_c>b.m_c)
 21         return 0;
 22     else
 23     {
 24         if (a.m_e>b.m_e)
 25             return 1;
 26         else
 27             return 0;
 28     }
 29 }
 30 
 31 int main()
 32 {
 33     int F;
 34     int Case = 1;
 35 
 36     cin >> F;
 37     while (F!=0)
 38     {
 39         int M,N,L;
 40         cin >> M >> N >> L;
 41         
 42         //count the number of job
 43         int totaljob = 0;
 44         
 45         //initialize
 46         job.clear();
 47         suspend.clear();
 48 
 49         //input
 50         for (int i = 0; i < L; i++)
 51         {
 52 
 53             int a,b,c,d,e,f,g;
 54 
 55             cin >> a >> b >> c >> d >> e >> f >> g;
 56 
 57             //Arraive before timeline
 58             if (c<F)
 59             {
 60                 rect *temp = new rect(a,b,c,d,e,f,g);
 61                 job.push_back(*temp);
 62                 totaljob++;
 63             }
 64         }
 65 
 66         //sort the jobs according to the arriving time
 67         sort(job.begin(),job.end(),compare);
 68 
 69         it = job.begin();
 70         long totalvalue = 0;
 71 
 72         for (int time = 0; time < F; time++)
 73         {
 74             int mm = M;
 75             int nn = N;
 76 
 77             while (it != job.end() && time >= it->m_c)
 78             {
 79                 suspend.push_back(*it);
 80                 it++;
 81             }
 82 
 83             vector<rect>::iterator temp;
 84             temp = suspend.begin();
 85             
 86             while (temp!=suspend.end())
 87             {
 88                 if (mm>=temp->m_a && nn>=temp->m_b)
 89                 {
 90                     mm-=temp->m_a;
 91                     nn-=temp->m_b;
 92                     totalvalue+=temp->m_e;
 93                     if (time + 1< temp->m_d)
 94                         totalvalue+=temp->m_f*(temp->m_d - time - 1 );
 95                     else if (time + 1 > temp->m_d)
 96                         totalvalue-=temp->m_g*(time + 1  - temp->m_d);                    
 97                     suspend.erase(temp);
 98                     temp = suspend.begin();
 99                 }
100                 else
101                     temp++;
102 
103             }
104         }
105 
106         vector<rect>::iterator temp;
107 
108         if (!suspend.empty())
109         {
110             for (temp = suspend.begin();temp!=suspend.end();temp++)
111             {
112                 if (temp->m_d<=F)
113                     totalvalue-=(F - temp->m_d)*temp->m_g;
114             }
115         }
116         //for (it = job.begin(); it!=job.end(); it++)
117         //    cout << it->m_a << " " << it->m_b << " " << it->m_c << " " << it->m_d << " " << it->m_e
118         //    << " " << it->m_f << " " << it->m_g << endl;
119 
120 
121 
122     cout << "Case " << Case++ << ": " << totalvalue << endl << endl;
123     cin >> F;
124     }
125     return 0;
126 }