每日一题分享|牛客小朋友做游戏详解＜每日一题分享＞ c++|游戏

题目：
文章图片

条件：

1.
闹腾的小朋友挨在一起的话就会出现打闹行为
导致游戏无法进行
【每日一题分享|牛客小朋友做游戏详解＜每日一题分享＞】故每个闹腾的小朋友两边必须是安静的小朋友
（选择参加游戏的小朋友必须满足安静小朋友的人数>或=闹腾小朋友人数）

图片解释：

文章图片

2.
要满足幸福度最大
就要将每个孩子的幸福度进行排序
选取两种不同的孩子使幸福度最大

分情况讨论：
情况1（不能选的情况）：
*1 n为偶数时n/2 大于所有的安静小朋友人数(原因：无法满足条件1)
*2 n为奇数时n/2 大于或等于所有的安静小朋友人数（原因：n为奇数时，安静小朋友至少要比闹腾小朋友多一个，不然无法满足条件1）
【该情况下无法满足条件，故输出"-1"】

情况2（在只通过条件2 选择小朋友后，发现选择参与游戏的安静小朋友个数多于闹腾小朋友个数）：
【满足条件1和条件2，直接输出】

情况3（在只通过条件2 选择小朋友后，发现选择参与游戏的闹腾小朋友个数多于安静小朋友个数，且与情况1 为相反的情况）：
该情况下要想取得幸福最大值
故只需要取刚好
1*n为偶数时安静小朋友取（n/2）闹腾小朋友取（n/2）
2*n为奇数时安静小朋友取（n/2+1）闹腾小朋友取（n/2）
【在满足条件1的情况下进行答案调整，输出答案】
代码思维导图：

文章图片

代码详解：

#include #include using namespace std; typedef long long ll; #include #include #include intA[(int)1e4 + 3]; intB[(int)1e4 + 3]; int main() { int t; ll a, b, n; cin >> t; while (t--) { memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); ll sum = 0, sa = 0, sb = 0; scanf("%lld%lld%lld", &a, &b, &n); for (int i = 0; i < a; i++) scanf("%d", &A[i]); for (int i = 0; i < b; i++) scanf("%d", &B[i]); sort(A, A + a, greater()); //将安静小朋友从大到小排序 sort(B, B + b, greater()); //将闹腾小朋友从大到小排序 if (2 * a < n)//情况1，不能围成一圈 { cout << "-1" << endl; continue; } for (ll i = 1; i <= n; i++)//进行情况判断 { if (A[sa] >= B[sb])//只通过幸福度大小进行小朋友选取 { sum += A[sa]; sa++; } else { sum += B[sb]; sb++; }if (i == n && sa < sb)//情况2，3判断 { sum = 0; for (int j = 0; j < n / 2; j++) { sum += A[j] + B[j]; } if (n & 1)//n为奇数 sum += A[n / 2]; } } printf("%lld\n", sum); } return 0; }

前缀和代码详解：

#include #include using namespace std; typedef long long ll; #include #include #include llA[(int)1e4 + 3]; llB[(int)1e4 + 3]; int main() { int t; ll a, b, n; cin >> t; while (t--) { memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); ll sum = 0, maxx = 0, tmb; scanf("%lld%lld%lld", &a, &b, &n); for (int i = 1; i <= a; i++) { scanf("%lld", &A[i]); } for (int i = 1; i <= b; i++) { scanf("%lld", &B[i]); } if (2 * a < n)//情况1，不能围成一圈 { cout << "-1" << endl; continue; } sort(A + 1, A + a + 1, greater()); //将安静小朋友从大到小排序 sort(B + 1, B + b + 1, greater()); //将闹腾小朋友从大到小排序 for (int i = 1; i <= max(a,b); i++)//前缀和 { A[i] += A[i - 1]; B[i] += B[i - 1]; } for (int i = 1; i <= n; i++) { ll tmb = n - i; if (i > a || tmb > b || i < tmb) continue; maxx = max(maxx, A[i] + B[tmb]); }//找到最大的幸福值 printf("%lld\n", maxx); } return 0; }

总结：考察对于条件的把握和细节的掌控，分情况讨论，前缀和等。
PS:本题也可以使用前缀和进行做题，感兴趣的可以自己尝试一下