本题是一个贪心题
先来讲讲思路吧
要算 S 最多能得多少巧克力,首先得把 C 和 S 的卡牌都排好序,核心思路就是让 S 用大的牌去赢 C 的小牌,越多越好。
这样每赢一次就能拿 3 颗巧克力。我们可以用两个指针,分别指着排序后 S 和 C 卡牌里最小或者最大的那个数,尽可能去凑 S 的牌点数比 C 大的情况,
然后统计 S 赢的次数。
如果把牌按降序排,然后从两端开始对比,如果 S 最大的牌比 C 最大的牌大,那这轮 S 就赢了;
要是 S 最大的牌没 C 大,那就用 S 最小的牌去和 C 最大的牌比,相当于牺牲小牌
。等统计完 S 赢的轮数后,剩下没配对的牌里,再去找点数相等的,这样能算平局次数,因为平局时两边各得 2 颗,
对 S 来说也能多拿分。最后 S 的得分就是用赢的次数乘以 3,加上平局次数乘以 2,再加上输的次数乘以 1
这就是本题的思路了
接下来是本题的AC代码
仅供参考!!!!
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int maxscore(vector<int>& A, vector<int>& B)//这里求最大分数
{
int n = A.size();
vector<int> a = A, b = B;
//排序
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int a_l = 0, a_r = n - 1;
int b_l = 0, b_r = n - 1;
int score = 0;
//开始贪心
while (b_l <= b_r)
{
//赢了的两种情况
if (b[b_r] > a[a_r])
{
score += 3;
b_r--;
a_r--;
}
else if (b[b_l] > a[a_l])
{
score += 3;
b_l++;
a_l++;
}
//否则
else
{
if (b[b_l] < a[a_r])//输了
score += 1;
else//没有输也没有赢,那就是平局
score += 2;
b_l++;
a_r--;
}
}
return score;//返回分数
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while (true)
{
int n;
if (!(cin >> n))
return 0;
if (n == 0)
break;
vector<int> C(n), S(n);
//输入数据
for (int i = 0; i < n; i++) cin >> C[i];
for (int i = 0; i < n; i++) cin >> S[i];
int smax = maxscore(C, S);//最大
int cmax = maxscore(S, C);
int smin = 4 * n - cmax;//最小
cout << smax << " " << smin << "\n";
}
return 0;
}