Skip the Class

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 624    Accepted Submission(s): 357 Problem Description Finally term begins. luras loves school so much as she could skip the class happily again.(wtf?) Luras will take n lessons in sequence(in another word, to have a chance to skip xDDDD). For every lesson, it has its own type and value to skip. But the only thing to note here is that luras can't skip the same type lesson more than twice. Which means if she have escaped the class type twice, she has to take all other lessons of this type. Now please answer the highest value luras can earn if she choose in the best way.   Input The first line is an integer T which indicates the case number. And as for each case, the first line is an integer n which indicates the number of lessons luras will take in sequence. Then there are n lines, for each line, there is a string consists of letters from 'a' to 'z' which is within the length of 10, and there is also an integer which is the value of this lesson. The string indicates the lesson type and the same string stands for the same lesson type. It is guaranteed that—— T is about 1000 For 100% cases, 1 <= n <= 100，1 <= |s| <= 10, 1 <= v <= 1000   Output As for each case, you need to output a single line. there should be 1 integer in the line which represents the highest value luras can earn if she choose in the best way.   Sample Input 2 5 english 1 english 2 english 3 math 10 cook 100 2 a 1 a 2   Sample Output 115 3 基本题意 ： 把每本书的价值加起来，如果该本书的次数出现了三次及其以上，则选出其中价值最高的两本书，如果次数小于三次，则把他们全部加起来。 方法：可以用map把书的名字和对应出现的次数存起来，再用一个vector把书的价值对存起来。 已经AC过的代码： #include <iostream> #include <cstring> #include <cstdio> #include <map> #include <vector> #include<algorithm> using namespace std; map<string,int> m; string s; int value; int n; vector<int> v[105]; int main() {     int t;     scanf("%d",&t);     int ans=0;     while(t--)     {         scanf("%d",&n);         int cot=0;         ans=0;         m.clear();//清空map         for(int i=1; i<=n; i++)             v[i].clear();//清空         for(int i=1; i<=n; i++)         {             cin>>s>>value;             if(!m[s]) m[s]=++cot;//记录字符串出现的次数             v[m[s]].push_back(value);//把字符串推入vector中         }         for(int i=1; i<=cot; i++)             sort(v[i].begin(),v[i].end());//对书的价值进行排序         for(int i=1; i<=cot; i++)         {             int l=v[i].size()-1;             ans+=v[i][l];             if(l>=1)                 ans+=v[i][l-1];         }         printf("%d\n",ans);     }     return 0; } 已经AC过的代码（问了一下队友的==）： #include <cstdio> #include <iostream> #include <cstring> #include <algorithm>           #include <map> using namespace std; struct ss {     string les;     int val; };//一节课和对应的价值 int cmp(ss x, ss y) {     if(x.les == y.les)         return x.val > y.val;//如果两节课是一门课，价值从大到小     else         return x.les > y.les;//如果不是一门课，字符串由大到小 } int main() {     int t, n, ans;     while(~scanf("%d",&t))     {         while(t--)         {             map<string, int> qq;//一门课和次数             ss f[105];             ans = 0;             scanf("%d",&n);             for(int i = 0; i < n; ++i)                 cin >> f[i].les >> f[i].val;             sort(f, f+n, cmp);             for(int i = 0; i < n; ++i)             {                 qq[f[i].les]++;//每门课对应的次数增加                 if(qq[f[i].les] <= 2) ans += f[i].val;             }             cout << ans << endl;         }     }     return 0; }