题解：P12860 [NERC 2020 Online] Kate' s 2021 Celebration

· · 题解

化竞生前来诈尸。

题目大意

Kate 要买一堆带数字的气球，这些气球必须能够组成数字 2021 。已知每组气球的价钱和每组气球所带的数字，问你买哪组气球能够组成 2021 并且最便宜。（大概是这个意思）

分析

首先，我们需要统计哪组气球能够组成数字 2021 。数字 2021 里面有两个 2，一个 0，一个1。所以我们扫描一遍这组气球，统计一下这三个数字出现的次数即可。

接下来我们再看价钱问题。我们可以把满足条件的气球组存到结构体数组中，结构体里面要定义序号和价钱，最后对价钱排一遍序，输出对应序号。我这里直接用 pair 定义数组。

多测记得清空。

#include<bits/stdc++.h>
using namespace std;
string s;
int price;
int j;
pair<int,int> a[100001];
int main(){
    int T;cin>>T;
    for(int t=1;t<=T;t++){//多测
        int zero=0,one=0,two=0;//0 1 2出现次数
        cin>>price>>s;
        for(int i=0;i<s.length();i++){//统计
            if(s[i]=='2') two++;
            if(s[i]=='0') zero++;
            if(s[i]=='1') one++;
        }if(two>=2&&zero>=1&&one>=1){//判断是否能组成2021，能了就存储下来
            a[++j].second=t;
            a[j].first=price;//对pair排序就是对主关键字排序，所以first要设置成价钱
        }
    }sort(a+1,a+j+1);//排序
    cout<<a[1].second;//输出对应序号

    return 0;
}

顺便感叹一句：洛谷变化挺大的