转杆

ReTF · 2025-05-20 08:11:43 · 题解

如何十行代码拿下（详细揭秘）

因为原问题显然不弱于直接求解最优解，直接观察最优解的性质容易得到最优解一定满足存在一组 n 条直线的大小为 \lfloor \dfrac{n}{2}\rfloor 的匹配，使得每组匹配的两条直线互相垂直。

然后考虑如何构造方案变成最优解，一个自然的思路是使用调整，观察到一个解如果可以将某条直线调整一步使得答案变更优，则他两边的直线数量是不平衡的，这启发我们在将直线按照 v 排序后，将上文所述的“匹配”构造为 (i,i+\lfloor\dfrac{n}{2}\rfloor)，其中 1\le i\le \lfloor\dfrac{n}{2}\rfloor。

然后以顺序将每组匹配的两条直线调整至垂直即可，尽管这很反直觉，但是手动模拟一下可以发现答案函数斜率始终非负。

#include"bits/stdc++.h"
int V[100010],I[100010];
void rotate(std::vector<int> t, int x);
bool cmp(int u,int v){return V[u]<V[v];}
void energy(int n, std::vector<int> v){
    for(int i=1;i<=n;i++)V[i]=v[i-1],I[i]=i;
    std::sort(I+1,I+n+1,cmp);
    for(int l=1,r=n/2+1;l<=n/2;l++,r++)
        rotate({I[r]-1},V[I[l]]+25000-V[I[r]]);
}