QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#848426 | #9989. Harmful Machine Learning | QOJQOJQOJ | WA | 0ms | 3576kb | C++14 | 3.9kb | 2025-01-08 20:25:14 | 2025-01-08 20:25:14 |
Judging History
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;
}
详细
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'