社区讨论
关于这个题
P2123皇后游戏参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mhjttctv
- 此快照首次捕获于
- 2025/11/04 08:24 4 个月前
- 此快照最后确认于
- 2025/11/04 08:24 4 个月前
CPP
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
double a[200010], b[200010];
LL c[200010];
int id[200010];
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
id[i] = i;
cin >> a[i] >> b[i];
//------------------------------------
a[i] += i * 0.000029;
b[i] += i * 0.000037;
//------------------------------------
}
sort(id + 1, id + n + 1, [](int x, int y)
{ return min(a[x], b[y]) < min(a[y], b[x]); });
LL sum = 0;
for (int x = 1; x <= n; x++)
{
sum += a[id[x]];
if (x == 1)
{
c[1] = a[id[1]] + b[id[1]];
}
else
{
c[x] = max(c[x - 1], sum) + b[id[x]];
}
}
// for (int i = 1; i <= n; i++)
// {
// cout << id[i] << ' ';
// }
// cout << '\n';
// for (int i = 1; i <= n; i++)
// {
// cout << c[i] << ' ';
// }
// cout << '\n';
cout << c[n] << '\n';
}
return 0;
}
注意到这个代码有一步莫名其妙的微扰,我发现这里只需要保证 乘的系数比 小(为了不影响最终结果)且对 不同就有很高的正确率(见记录)
那么这东西有什么正确性吗,或者说如果有正确性的话这两个数满足什么特点吗
回复
共 1 条回复,欢迎继续交流。
正在加载回复...