HDU 6015-Skip the Class（模拟-结构体排序）

红太狼 2022-07-10 10:00 87阅读 0赞

# Skip the Class #

Accepts: 678

Submissions: 1285

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

终于又开学啦。呃喵最喜欢的就是开学了，因为这样她又可以愉快地翘课了（啊？）
    呃喵接下来有n节课程需要上（换句话说，可以翘。）
    每节课程有相应的课程类型与课程翘课价值。
    有一点需要注意的是，呃喵不可以翘同一类课程超过两次，就是如果这类课已经翘了两次，接下来就一定要上。
    问你在这个条件下，呃喵可以获得的最大翘课价值。

输入描述

第一行为一个整数T，代表数据组数。
    接下来，对于每组数据——
    第一行一个整数n，表示接下来需要依次上的课程数量，
    接下来有n行，每行包括一个仅由'a'~'z'构成的长度不超过10的字符串s与一个正整数v。
    其中字符串表示课程的类型，相同的字符串代表相同的课程。
    
    数据保证——
    1 <= T <= 1000
    对于每组数据，1 <= n <= 100，1 <= |s| <= 10, 1 <= v <= 1000

输出描述

对于每组数据，输出一行。
    该行有1个整数，表示呃喵可以获得的最大翘课价值。

输入样例

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

输出样例

115
    3

[Statistic][] | [Submit][] | [Clarifications][] | [Back][]

## 解题思路： ##

读入数据，用结构体保存某门课的名称、不同价值和出现次数，将同一门课的不同价值保存到一个数组中。

for循环各门课，将其不同价值降序排列；然后依次最多取每门课的最大两个价值相加。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 110
    struct Node
    {
        string na;//课程名称
        int v[MAXN];//课程价值
        int cv;//课程出现次数
    } a[MAXN];
    int cmp(int a,int b)//结构体排序
    {
        return a>b;//对价值降序排列
    }
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            int n,k=0,ans=0;
            string s;
            int temp;
            cin>>n;
            for(int i=0; i<n; ++i)
            {
                bool flag=false;
                a[i].cv=0;
                cin>>s>>temp;
                for(int j=0; j<k; ++j)//判断当前课程名称是否出现过
                {
                    if(a[j].na==s)//已经出现
                    {
                        a[j].v[a[j].cv++]=temp;
                        flag=true;
                        break;
                    }
                }
                if(!flag)//没出现过的话要新加入
                {
                    a[k].na=s;
                    a[k].v[a[k].cv++]=temp;
                    ++k;//不同课程的数目
                }
            }
            for(int i=0; i<n; ++i)//对各个课程中的不同价值降序排列
                sort(a[i].v,a[i].v+a[i].cv,cmp);//排序
            /*for(int i=0; i<n; ++i)
            {
                for(int j=0; j<a[i].cv; ++j)
                    cout<<a[i].v[j]<<" ";
                cout<<endl;
            }*/
            for(int i=0; i<n; ++i)
            {
                int cf=0;
                for(int j=0; j<a[i].cv; ++j)
                {
                    if(cf==2) break;//翘了两次
                    ans+=a[i].v[j];
                    ++cf;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    /*
    2
    5
    english 1
    english 2
    english 3
    math 10
    cook 100
    2
    a 1
    a 2
    */

[Statistic]: http://bestcoder.hdu.edu.cn/contests/contest_statistic.php?cid=748&pid=1001
[Submit]: http://bestcoder.hdu.edu.cn/contests/contest_submit.php?cid=748&pid=1001
[Clarifications]: http://bestcoder.hdu.edu.cn/contests/contest_listtopic.php?cid=748
[Back]: http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=748&pid=1001#