HDU6015 Skip the Class

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.

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

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.

  
  

   
   2
5
english 1
english 2
english 3
math 10
cook 100
2
a 1
a 2
  
  

  
  

   
   115
3
  
  

题意：给你n组测试数据，每组测试数据的第一行是一个数字t，表示接下来有t行，每行有课程的名称和它的价值，同种类型的课 luras最多只能翘两次，那么问你对于每组测试数据，luras最多能够翘掉多少分？

这里有两种解决办法：一种是用数组，一种是用STL。我觉得如果STL用的比较熟练，第二种方法比较好

同种课程排在一起，同时分数从高到低

第一种：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
    string s;
    int val;
}a[200];
bool cmp(node a,node b)
{
    if(a.s==b.s)
        return a.val>b.val;
    return a.s>b.s;
}
int main()
{
    int n,sum,i,j;
    cin>>n;
    int l;
    while(n--)
    {
        int t;

        cin>>t;
        for(i=0;i<t;i++)
            cin>>a[i].s>>a[i].val;
        sort(a,a+t,cmp);
        sum=a[0].val;
        l=1;
        for(i=1;i<t;i++)
        {
            if(a[i].s==a[i-1].s)
            {
                if(l<2)
                {
                    sum=sum+a[i].val;
                    l++;
                }
            }
            else
            {
                l=1;
                sum=sum+a[i].val;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

第二种：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#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;
}