社区讨论

关于这个题

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;
}
注意到这个代码有一步莫名其妙的微扰,我发现这里只需要保证 ii 乘的系数比 120000\frac{1}{20000} 小(为了不影响最终结果)且对 a,ba,b 不同就有很高的正确率(见记录)
那么这东西有什么正确性吗,或者说如果有正确性的话这两个数满足什么特点吗

回复

1 条回复,欢迎继续交流。

正在加载回复...