AT_abc139_f 题解

Comet387 · 2023-07-20 10:00:44 · 题解

本题解为非正解。

前言

此题 N 很小、答案很密集，所以随机化算法可以 AC。

思路

如果直接贪心，肯定会 WA，但是交换点的顺序再贪心，就可能得到正确答案。

考虑枚举点顺序，时间复杂度 \mathcal O(n!\times n) 肯定会 TLE。

所以我们可以每次随机打乱 N 个点的顺序（直到即将超过时间限制再退出），贪心计算后取最大值，就能 AC 了。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
double ans;
struct node
{
    int x,y;
}a[101];
void SA()
{
    mt19937 rnd(114514);
    while(clock()*1.0/CLOCKS_PER_SEC<1.9) // 程序运行时间大于 1.9 秒后退出
    {
        shuffle(a+1,a+n+1,rnd); // 随机打乱顺序
        int nxtx=0,nxty=0;
        double res=0;
        for(node i:a) // 贪心求值
            if(hypot(nxtx+i.x,nxty+i.y)>hypot(nxtx,nxty))
                nxtx+=i.x,nxty+=i.y,res=hypot(nxtx,nxty);
        ans=max(ans,res); // 答案取最大值
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
    SA();
    cout<<fixed<<setprecision(100)<<ans; // 保留 100 位小数输出（其实不需要这么多位）
    return 0;
}