昨天在牛客网打了第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛(同步赛),我这个菜鸡才AC了五条题目,真的是太菜了。然后这个F题,我一直被卡时间,说多了都是泪啊,先看看我的惨痛战绩:

这..真的是令人难过。

时间限制1s,内存32MB

去年的新冠疫情爆发让众多大学生只能只能在家里上学,老师为了方便自己录入成绩和方便大家成绩查询,建立了一个录入和查询成绩的系统,能完成M次两种不同的查询,输入查询次数M,查询M次,每次首先输入查询的模式T,T为1时,输入同学的姓名Name,并依次输出同学的成绩Grade(0<=Grade<=100), 学号(0~1000000},性别(1/2),T为2时,输入成绩,输出有具体有哪些同学考到了这个分数,输出同学的Name,并要求按字典序输出,当没有同学为此分数时,则不输出。字典序,对于字符串,先按首字符排序,如果首字符相同,再按第二个字符排序,以此类推。
输入描述:
第一行包含一个整数N,表示系统中共有N个人(1<=N<=100000)。 下面N行分别输入N个人的姓名Name,成绩Grade(成绩在0~100之间),性别(1或2分别表示男性、女性),学号。表示系统中成员的信息 输入查询次数M(M<=10000000),接下来M行完成M次查询任务
输出描述:
输出M次查询的结果,当T为1时,输入同学的姓名Name,并在一行中依次输出同学的成绩Grade(0<=Grade<=100), 学号(0~1000000},性别(1/2),用空格间隔(注意行末无空格),T为2时,输入成绩,输出有具体有哪些同学考到了这个分数,输出同学的Name(每个Name输出一行,无空格),并要求按字典序输出,当没有同学为此分数时,则不输出。

示例1
输入

5
N 28 2 7475
UN 83 2 27550
EXF 5 2 17298
OVYNH 51 2 14827
XNV 53 1 7591
2
1
XNV
2
27

输出

53 7591 1

这题我最开始犯了错误就是,没想到一个很好的方式来表示这些数据,我最开始采用的是把数据弄到两个相同的数组里面,然后各自按照姓名和分数来进行快速排序,毫无疑问TLE了。

后来,想到把每个分数的同学的名字都各自存到一个数组里面,那么在按照分数查名字的时候,对相应的数组进行快排然后输出就好了。

对于按名字查信息的话,就用map来实现,这个就比较简单。

可是,即使这样,还是TLE了。百思不得其解。最后想了想,改了输出的代码,把string转为char*,然后用puts来输出,速度就快了很多,终于成功AC了。

其实想想,这也不是第一次被IO卡时间了,有时候总是被卡时间的时候,优化了算法复杂度还不行的话,就考虑一下IO的问题。

AC代码:

#include <stdio.h>
#include<cstdio>
#include <algorithm>
#include <string.h>
#include <string>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;

#define MAXN 100005

struct stu
{
    string name;
    int id, grade, sex;
}st[MAXN];


bool cmp_name(const stu &a, const stu &b)
{
    return a.name < b.name;
}


int main()
{
    
    
    //cout.tie(0);
    map<string, int> mp;
    vector<string> vec[101];
    //ll js_s[102] = {0};
    int n;
    scanf("%d", &n);

    
    for (int i = 0; i < n; ++i)
    {
        cin >> st[i].name;
        scanf("%d%d%d",&st[i].grade, &st[i].sex, &st[i].id);
        
        mp[st[i].name] = i;
        vec[st[i].grade].push_back(st[i].name);
        //cin >> st[i].name >> st[i].grade >> st[i].sex >> st[i].id;
    }

    for(int i=0;i<=100;++i)
        sort(vec[i].begin(),vec[i].end());

    int m;
    scanf("%d", &m);

    int t;

    //cout << js_s[27] << endl;
    string s;
    while (m--)
    {
        scanf("%d", &t);
        if (t == 1) //用名字查成绩
        {

            cin>>s;
            int tmp = mp[s];

            printf("%d %d %d\n", st[tmp].grade, st[tmp].id, st[tmp].sex);
            //cout << st[idx].grade << " " << st[idx].id << " " << st[idx].sex << endl;
        }
        else
        {
            int score;
            //cin >> score;
            scanf("%d", &score);
            //cout << score << endl;
            
            for(string x:vec[score])
            {
                puts(x.c_str());
                //printf("\n");
            }
        }
    }
}

转载请注明出处:https://www.longjin666.top/?p=756

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注