CF2A Winner

Loner_Knowledge · 2018-01-29 08:26:03 · 题解

此题是一道字符串模拟题

此题的题意就是计算出最高分后，在最后得分为最高分的玩家们中，找那个过程分数最先大于等于最高分的玩家并输出他的名字。

此题的坑点在于最先得到的分数大于等于最高分这里，这代表在计算完最高分后还需要再重新进行一遍加分的过程，在过程中寻找答案。

可以用STL中的map来做，只需要map<string,int>就可以方便的写出代码，但如果不用STL就需要自定义指针。

非STL代码

#include<cstdio>
#include<cstring>
using namespace std;
const int Inf=0x7FFFFFFF;
struct Map {
    int sum;
    int t;
    char *p_s;
}M[1002];        //这是一个栈，存储玩家名称和玩家的最后分数与过程分数
struct Data {
    char str[35];
    int score;
    Map *p_M;
}D[1002];
bool Check(const char *a,const char *b) {    //这是一个比较字符串的函数，如果不写也可以用strcmp代替
    if(strlen(a)!=strlen(b))
        return 0;
    for(int i=0;a[i];++i)
        if(a[i]!=b[i])
            return 0;
    return 1;
}
int main() {
    int n,m=0,Max=-Inf,p=0;        //Max取负数是由于有负数数据
    scanf("%d",&n);
    for(int i=1,j;i<=n;++i) {
        scanf("%s%d",D[i].str,&D[i].score);
        for(j=1;j<=m;++j)
            if(Check(M[j].p_s,D[i].str))    //在栈中查找
                break;
        D[i].p_M=&M[j];            //更新指针
        M[j].p_s=D[i].str;        //更新指针
        M[j].sum+=D[i].score;    //更新总分数
        if(j>m)        //如果j>m代表当前栈内没有该玩家
            ++m;    //入栈
    }
    for(int i=1;i<=m;++i)
        if(M[i].sum>Max)
            Max=M[i].sum;    //在总分数计算完后寻找最大值
    for(int i=1;i<=n&&!p;++i) {
        D[i].p_M->t+=D[i].score;
        if(D[i].p_M->sum==Max&&D[i].p_M->t>=Max)    //在最后得分为最高分的玩家中，寻找过程分数最先大于等于最高分的玩家
            p=i;    //一旦赋值为i，i必定非零，由于循环的!p条件自动跳出循环
    }
    printf("%s",D[p].str);
    return 0;
}

STL代码

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
using namespace std;        //皆同上所述
const int Inf=0x7FFFFFFF;
struct Data {
    string str;
    int score;
}D[1002];
map<string,int> m,t;
int main() {
    int n,Max=-Inf,p=0;
    scanf("%d",&n);
    for(int i=1,num;i<=n;++i) {
        cin>>D[i].str;
        scanf("%d",&D[i].score);
        m[D[i].str]+=D[i].score;
    }
    for(int i=1;i<=n;++i)
        if(m[D[i].str]>Max)
            Max=m[D[i].str];
    for(int i=1;i<=n&&!p;++i) {
        t[D[i].str]+=D[i].score;
        if(m[D[i].str]==Max&&t[D[i].str]>=Max)
            p=i;
    }
    cout<<D[p].str;
    return 0;
}