QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848426#9989. Harmful Machine LearningQOJQOJQOJWA 0ms3576kbC++143.9kb2025-01-08 20:25:142025-01-08 20:25:14

Judging History

你现在查看的是最新测评结果

  • [2025-01-08 20:25:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3576kb
  • [2025-01-08 20:25:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

/*
  博弈结论总结版:
  - 若某数 v 在数组里出现频次 >= 3, 则可拿到 v
  - 若出现频次 = 2, 需要有一个更大的数做诱饵(出现次数 >= 1), 才可拿到 v
  - 若出现频次 = 1, 需要有一个更大的数做诱饵(出现次数 >= 1), 才可拿到 v
    (实际实现里,会发现“更大数只有 1 份”也有可能行得通,
     因为那 1 份更大数就是最优先被换走的目标。)
*/

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n, x;
        cin >> n >> x;  // x 实际并不影响我们按“结论”算答案
        vector<long long> arr(n);
        for(int i=0; i<n; i++){
            cin >> arr[i];
        }

        // 统计出现次数
        unordered_map<long long,int> cnt;
        cnt.reserve(n);
        cnt.max_load_factor(0.7f);
        for(auto &v: arr){
            cnt[v]++;
        }

        // 去重并降序
        vector<long long> vals;
        vals.reserve(cnt.size());
        for(auto &kv : cnt){
            vals.push_back(kv.first);
        }
        sort(vals.begin(), vals.end(), greater<long long>());

        // 扫描
        long long ans = 0; 
        // 最小也能拿到数组里的某个值——万一数组全是0,就0;否则肯定 >= 0
        // 可以先把 ans 定成 0,后面看不到更大就保底 0.
        // 但一般可以把 ans 至少设成 max(...)
        // 这里为了与题意“输出能拿到的最大分”一致,最后如果什么都不匹配,
        // 说明只能拿到 vals.back() 这样的最小值,也要比 0 大。
        // 不过大多数时候我们会在循环里 break 掉。

        // 为了快速判断“是否有比 vals[i] 更大的数”
        // 其实只要 i > 0,就说明上面有更大的数 ( 因为 vals 是降序 )。
        // 是否“出现次数 >= 1” 肯定是 >=1, 否则它不会在 vals 里。
        // 所以只要 i>0,就表示确实存在更大的诱饵。
        // (如果需要再严格,可在 i>0 的时候看看 cnt[vals[0...(i-1)]] 是否都>0 —— 但肯定>0)

        bool found = false;
        for(int i=0; i<(int)vals.size(); i++){
            long long v = vals[i];
            int c = cnt[v];

            // case 1: freq >= 3
            if(c >= 3){
                ans = v;
                found = true;
                break;
            }

            // case 2: freq = 2
            // 若 v 是全局最大(i=0),则没有更大数可诱饵,拿不到 v;
            // 若 i>0,说明至少有一个更大的数 vals[0]...vals[i-1],可作诱饵。
            if(c == 2){
                if(i > 0){ 
                    ans = v;
                    found = true;
                    break;
                }
                // 否则拿不到
            }

            // case 3: freq = 1
            // 需要至少有一个更大的数 ( i>0 ) 才行
            if(c == 1){
                if(i > 0){
                    ans = v;
                    found = true;
                    break;
                }
            }
        }

        // 若以上都没 break,说明所有数都无法用“更大的数做诱饵”或“自己多份”来保留,
        // 按道理应该只剩下一个可能:整个数组可能全是同一个数,且它的出现次数 < 3,
        // 或者它本身就是最小的数。那 BOT 只能拿到它了;或者干脆全是 0。
        // 这里就拿 vals.back() 兜底。
        if(!found){
            // 至少可以拿到数组里最小的那个(或者 0)
            // 不过通常题意都会让咱们输出“能拿到的最大分数”,
            // 所以这里如果实在进不来,也可以写成:
            ans = vals.back();  
        }

        cout << ans << "\n";
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3576kb

input:

4
3 2
1 2 3
13 4
1 1 4 5 1 4 1 9 1 9 8 1 0
4 2
1 10 100 1000
1 1
114514

output:

2
8
100
114514

result:

wrong answer 1st lines differ - expected: '3', found: '2'