历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1800. 不做最后一个！【模拟氵题详解，并且解释一个Bug】附送打表代码（逃原题链接简单

作者：

Conan15 , 2022-04-04 21:17:39 , 所有人可见 , 阅读 1848

20

2

宣传一下$\Huge\color{green}{春季每日一题题解}$

此题为氵题（逃
就是读入每一头奶牛，并累计它们的产奶量，最后按照题意模拟即可，如果一些细节处不懂的可以留言！

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> m;
const string w[] = {"", "Bessie", "Elsie", "Daisy", "Gertie", "Annabelle", "Maggie", "Henrietta"};
struct S{ int a; string b; } x[10];
int cmp(S a, S b) {return a.a < b.a;}
int main() {
    int n; cin>>n;
    if (n == 1) {string x; cin>> x; cout << x; return 0;}
    while (n--) {
        string s; int e;
        cin >> s >> e;
        m[s] += e;
    }
    for (int i = 1; i <= 7; i++) x[i].a = m[w[i]], x[i].b = w[i];
    sort(x + 1, x + 8, cmp);
    int p = 1; while (x[p].a == 0) p++;
    if (x[p].a == x[7].a) {puts("Tie"); return 0;} //无解
    int s = 2;
    while (x[s].a == x[s - 1].a && s < 7) s++;
    cout << x[s].b << endl;
    return 0;
}

但是大家会发现……

这个代码会WA一个点！

这个点就是新增的数据。
那么问题在哪里呢？
问题就出在没加特判。0属于最小的一个值，所以非零正整数中的最小的一个，如果出现了多个，那么结果就应该是Tie。
所以我们要对代码进行改进：

#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> m;
const string w[] = {"", "Bessie", "Elsie", "Daisy", "Gertie", "Annabelle", "Maggie", "Henrietta"};
struct S{ int a; string b; } x[10];
int cmp(S a, S b) {return a.a < b.a;}
int main() {
    int n; cin>>n;
    if (n == 1) {string x; cin>> x; cout << x; return 0;}
    while (n--) {
        string s; int e;
        cin >> s >> e;
        m[s] += e;
    }
    for (int i = 1; i <= 7; i++) x[i].a = m[w[i]], x[i].b = w[i];
    sort(x + 1, x + 8, cmp);
    if (x[1].a == x[7].a) {puts("Tie"); return 0;} //无解
    int s = 2;
    while (x[s].a == x[s - 1].a && s < 7) s++;
    if (x[s].a != x[s + 1].a) cout << x[s].b << endl;
    else puts("Tie");
    return 0;
}
//0属于最小的一个，所以只要是非零的最小值有两个就是Tie。

关于某大佬送的打表代码……

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==10) cout<<"Henrietta"<<endl;
    else if(n==1) cout<<"Annabelle"<<endl;
    else if(n==2) cout<<"Tie"<<endl;
    else if(n==15) cout<<"Gertie"<<endl;
    else if(n==20) cout<<"Elsie"<<endl;
    else if(n==30) cout<<"Elsie"<<endl;
    else if(n==40) cout<<"Bessie"<<endl;
    else if(n==60) cout<<"Bessie"<<endl;
    else if(n==80) cout<<"Elsie"<<endl;
    else if(n==100) cout<<"Annabelle"<<endl;
    else cout<<"Tie"<<endl;
    return 0;
}

~~这至少让我们知道了数据范围~~

42 评论

w1r 2022-04-06 22:54

真正的面向答案编程！！！

Conan15 2022-04-07 12:51

hhhhhhhhhhhhhh

Ethereal_60 2022-04-08 16:33

我觉得是面向失业编程hhhh

Conan15 2022-04-09 20:59 回复了 Ethereal_60 的评论

hhh

lklk 2022-04-06 15:46

大佬想问下unordered_map和普通的map有什么区别吗，之前一直用的都是map没用过unordered_map

Conan15 2022-04-06 19:51

听说……unordered_map是O(1)的，map是O(log n)的

椒盐土豆 2022-04-05 15:38

暴力就完事了

#include<bits/stdc++.h>
using namespace std;
int n, m, a;
unordered_map<string, int> kmap;
string s, crow[7]={"Bessie","Elsie","Daisy","Gertie","Annabelle","Maggie","Henrietta"};
int d[1000];
int main(){
    scanf("%d", &n);
    m = n;
    for (int i = 0; i < 7; i ++ )
        kmap[crow[i]] = 0;
    while (m -- ){
        cin>>s>>a;
        kmap[s]+=a;
    }
    a = 0;
    for(auto [b, c]: kmap){
        d[a++] = c;
    }
    sort(d , d+a);

    if(d[0]==d[a-1])cout<<"Tie"<<endl;
    else{
        int flag = d[0];
        for(int i = 1; i < a; i ++ ){
            if(d[i]>flag && d[i] == d[i + 1]){
                cout<<"Tie"<<endl;
                return 0;
            }
            if(d[i]>flag){
                flag = d[i];
                break;
            }
        }
        for(auto [b, c]: kmap){
            if(c==flag)cout<<b<<endl;
        }
    }

}

Conan15 2022-04-05 18:20

嗯嗯，辛苦了，还来看我这垃圾题解hh

椒盐土豆 2022-04-05 19:38 回复了 Conan15 的评论

看看大佬题解, 康康有没有方便方法

陆修远 2022-04-26 21:22 回复了 Conan15 的评论

阿巴

陆修远 2022-04-26 21:22 回复了 Conan15 的评论

我给你换了一种写法：

#include<bits/stdc++.h>
using namespace std;
int main () {
    int n;
    cin>>n;
    string ans[10000]={};
    for (int i=0;i<10000;++i) ans[i]="Tie";
    ans[10]="Henrietta";
    ans[1]=ans[100]="Annabelle";
    ans[2]="Tie";
    ans[15]="Gertie";
    ans[20]=ans[30]=ans[80]="Elsie";
    ans[40]=ans[60]="Bessie";
    cout<<ans[n];
    return 0;
}

Conan15 2022-04-26 22:26 回复了陆修远的评论

Oh！Thanks！

陆修远 2022-04-27 08:12 回复了 Conan15 的评论

这玩意更简洁，~~大佬当时是不是没有想到（逃）~~

是莎莎呀 2022-04-05 14:54

可以不用排序，遍历找第二小的就可以啦

#include<iostream>
#include<unordered_map>

#define x first
#define y second

using namespace std;

int n;
unordered_map<string, int> mp;

int main(){

    cin >> n;

    string s;
    int x;
    for(int i = 0; i < n; i++){

        cin >> s >> x;
        mp[s] += x;
    }

    int a1, a2;
    a1 = 1e9;
    a2 = 2e9;
    for(auto &t: mp){

        //if(!a1) a1 = t.y;
        if(a1 < t.y && t.y < a2) a2 = t.y;
        else if(t.y < a1) a2 = a1, a1 = t.y;
    }

    if(mp.size() < 7) a2 = a1, a1 = 0;

    int cnt = 0;
    for(auto &t: mp)
        if(t.y == a2) cnt++, s = t.x;

    if(cnt != 1) puts("Tie");
    else cout << s << endl;

    //cout << mp["Bessie"] << ' ' << mp["Annabelle"];

    return 0;
}