碎碎念
- AC完37题，本题是浙江2008年省选的一道题，很顺利的AC掉，本题思维难度一般，谢谢题主大人，喜提一道
提高 /省选-
题目：P2587 [ZJOI2008]泡泡堂
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P2587
- 参考题解：https://www.luogu.com.cn/problem/solution/P2587
- 标签：
OI、贪心 - 难度：
提高 /省选-
题解
思路
- 是一道田忌赛马模版题？？？
- 己方最优策略就是把自己当成田忌
- 最劣就是把对方当田忌，求对方最优策略
- 然后我们惊喜且愉快地发现，每轮比赛一共有2分，谁赢了谁拿走2分，输了不倒扣分，平局就是双方平分这2分，也就是1人1分
- 于是乎，对方最优时，己方的分数就是n轮下来供双方赢取的分数减去对方最多能拿到的分数（2n - 对方最优分数）
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
int score(vector<int> t, vector<int> k, int n) {
int rt, rk, lt, lk;
int ans = 0;
rt = n - 1;
rk = n - 1;
lk = 0;
lt = 0;
for (int i = 0; i < n; i) {
if (t[lt] > k[lk]) {
ans = 2;
lt;
lk;
} else if (t[rt] > k[rk]) {
--rt;
--rk;
ans = 2;
} else if (t[rt] < k[lk]) {
--rt;
lk;
} else if (t[rt] == k[lk]) {
ans = 1;
--rt;
lk;
}
}
return ans;
}
void best_coder() {
int n;
cin >> n;
vector<int> k(n);
vector<int> t(n);
for (int i = 0; i < n; i) {
cin >> t[i];
}
for (int i = 0; i < n; i) {
cin >> k[i];
}
sort(t.begin(), t.end(), greater<int>());
sort(k.begin(), k.end(), greater<int>());
cout << score(t, k, n) << " " << 2 * n - score(k, t, n);
}
void happy_coder() {
}
int main() {
// // 提升cin、cout效率
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
/**
【Input】
2
1
3
2
4
【Output】
2 0
【Input】
6
10000000
10000000
10000000
10000000
10000000
10000000
0
0
0
0
0
0
【Output】
12 12
*/END
