字体设计比较好的网站,建设厅网站查询电工证件,个人可以做哪些有意思的网站,wordpress与微信连接数据库一道练手的题#xff0c;思路很快就能出来#xff0c;练习简化的用语言去实现 题目链接
题目大意
两个人比赛#xff0c;现在已经进行了 n n n轮#xff0c;给定两行、每行 n n n个正整数作为每轮的分数#xff0c;每人总分计算方法为#xff0c;得分从大到小排前 n / …一道练手的题思路很快就能出来练习简化的用语言去实现 题目链接
题目大意
两个人比赛现在已经进行了 n n n轮给定两行、每行 n n n个正整数作为每轮的分数每人总分计算方法为得分从大到小排前 n / 4 n/4 n/4个的和接下来每轮每人可能得分为 x ( 0 x 100 ) x(0x100) x(0x100)问最小多少轮后第一个人分数高于第二个人
思路
很容易想到用先排序再前缀和处理一下得分 如果第一个人总分小于第二个人 再思考如何分配后面的轮次 显然最差情况是再来 n n n轮结果完全反过来使得两人分数相等 思考发现最优情况是每轮让第一个人 100 100 100第二个人 0 0 0 所以方法出来了循环实现上述语句 发现直接模拟的话实现很麻烦而且可能会 T T T掉 所以考虑每轮分数之间的关系 考虑第一个人每次加 100 100 100分都会再减去被选中的分数中的最小值所以总共第 k k k轮补加的第 i i i轮后第一个人的有效分数段数为 n k − k / 4 nk-k/4 nk−k/4分数为 i ∗ 100 p r e a [ n − i ] i*100prea[n-i] i∗100prea[n−i] 考虑第二个人每次是加 0 0 0分显然如果还有没有加上的分数会优先被加入总分 当轮数大于有效分数的数量时总分保持不变
ACcode
#includebits/stdc.husing namespace std;using ll long long;bool cmp(int x, int y) {return x y;
}void solve()
{int n;cin n;vectorinta(n 3), b(n 3);for (int i 1;i n;i)cin a[i];for (int i 1;i n;i)cin b[i];vectorllpa(n 3), pb(n 3);sort(a.begin() 1, a.begin() 1 n, cmp);sort(b.begin() 1, b.begin() 1 n, cmp);pa[0] 0;pb[0] 0;for (int i 1;i n;i)pa[i] pa[i - 1] a[i];for (int i 1;i n;i)pb[i] pb[i - 1] b[i];int ans 0;for (;;ans) {int k n ans;int d k - k / 4;ll suma 100 * ans pa[d - ans];ll sumb d n ? pb[d] : pb[n];if (suma sumb) {cout ans \n;return;}}
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin t;while (t--) {solve();}return 0;
}
