@xunuo
2017-02-26T10:19:30.000000Z
字数 2114
阅读 1045
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
结构体
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.
(终于又开学啦。呃喵最喜欢的就是开学了,因为这样她又可以愉快地翘课了(啊?)
呃喵接下来有n节课程需要上(换句话说,可以翘。)
每节课程有相应的课程类型与课程翘课价值。
有一点需要注意的是,呃喵不可以翘同一类课程超过两次,就是如果这类课已经翘了两次,接下来就一定要上。
问你在这个条件下,呃喵可以获得的最大翘课价值。)
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
(第一行为一个整数T,代表数据组数。
接下来,对于每组数据——
第一行一个整数n,表示接下来需要依次上的课程数量,
接下来有n行,每行包括一个仅由'a'~'z'构成的长度不超过10的字符串s与一个正整数v。
其中字符串表示课程的类型,相同的字符串代表相同的课程。
数据保证——
1 <= T <= 1000
对于每组数据,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.
(对于每组数据,输出一行。
该行有1个整数,表示呃喵可以获得的最大翘课价值。)
2
5
english 1
english 2
english 3
math 10
cook 100
2
a 1
a 2
115
3
题意:
有中文......
解题思路:
结构体排个序,然后再标记一下出现的课程的个数。
完整代码:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define N 1010
struct node
{
char s[15];
int v;
}a[N];
bool cmp(node x,node y)
{
if(x.v<y.v)
return x.v<y.v;
return x.v>x.v;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s%d",a[i].s,&a[i].v);
sort(a,a+n,cmp);
int sum=a[n-1].v;
for(int i=n-2;i>=0;i--)
{
int flag=0;
for(int j=n-1;j>i;j--)
if(strcmp(a[i].s,a[j].s)==0)
flag++;
if(flag<2)
sum+=a[i].v;
}
printf("%d\n",sum);
}
return 0;
}