题解：P12543 嘟嘟嘟

· · 题解

将直线按一二象限分类，0 归一象限，25000 归二象限。

考虑最终应该构造一些十字对（两条直线相垂直）。

注意到十字对对于其他直线贡献固定，猜想一堆十字对带至多一条直线最优。

所以考虑两两一组归于坐标轴，形成十字对。

若一象限线严格多于二象限线，则将一象限线最靠近 x,y 轴的两条直线一条一条移动到坐标轴。

二象限线严格多于一象限线，同理。

若一象限线、二象限线数量相等，将二象限线最靠近 y 的 a、一象限线最靠近 x 的 b。两条一起旋转，a 往 y 方向转，b 往 x 方向转，使离目标坐标轴近的移动至坐标轴，再一步操作另一条移动至坐标轴。

显然一象限线、二象限线最多各剩一条。

然后变成 n=2 按最后一种做就行，n=1 不用管。

证明能量不减：可以考虑移动单条直线，贡献提高的线的数量多于贡献减少的线的数量，多直线同理。

这是 n 次操作，移动至多 2n 条线的解法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e6+5,inf=1e18,mod=1e9+7;
ll l1,r1,l2,r2,d;
struct node{ll x,id;}b[N];
void rotate(std::vector<int>t,int x);
inline bool cmp(node u,node v){return u.x<v.x;}
void energy(int n,std::vector<int>v){
    for(int i=0;i<n;i++) b[i+1]=node{v[i],i};
    sort(b+1,b+n+1,cmp);
    l1=1,r2=n;r1=0;
    for(int i=1;i<=n;i++) if(b[i].x<25000) r1=i;
    l2=r1+1;
    while((l1<r1)||(l2<r2)){
        if((r1-l1)>(r2-l2)){
            // case1
            rotate({b[l1].id},0-b[l1].x);
            rotate({b[r1].id},25000-b[r1].x);
            l1++,r1--;
        }
        else if((r1-l1)<(r2-l2)){
            // case2
            rotate({b[l2].id},25000-b[l2].x);
            rotate({b[r2].id},50000-b[r2].x);
            l2++,r2--;
        }
        else{
            // case3
            d=min(b[l2].x-25000,b[l1].x-0);
            rotate({b[l1].id,b[l2].id},-d);
            if(b[l2].x-25000>=b[l1].x-0) rotate({b[l2].id},-(b[l2].x-25000-d));
            else rotate({b[l1].id},-(b[l1].x-0-d));
            l1++,l2++;
        }
    }
    if((l1==r1)&&(l2==r2)){
            // case3
            d=min(b[l2].x-25000,b[l1].x-0);
            rotate({b[l1].id,b[l2].id},-d);
            if(b[l2].x-25000>=b[l1].x-0) rotate({b[l2].id},-(b[l2].x-25000-d));
            else rotate({b[l1].id},-(b[l1].x-0-d));
            l1++,l2++;
    }
}