题解：P12543 嘟嘟嘟

将直线按一二象限分类，

0

归一象限，

25000

归二象限。

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

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

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

若一象限线严格多于二象限线，则将一象限线最靠近

x,y

轴的两条直线一条一条移动到坐标轴。

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

若一象限线、二象限线数量相等，将二象限线最靠近

y

的

a

、一象限线最靠近

x

的

b

。两条一起旋转，

a

往

y

方向转，

b

往

x

方向转，使离目标坐标轴近的移动至坐标轴，再一步操作另一条移动至坐标轴。

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

然后变成

n=2

按最后一种做就行，

n=1

不用管。

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

这是

n

次操作，移动至多

2n

条线的解法。

CPP

#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++;
	}
}

题解：P12543 嘟嘟嘟

文章操作

相关推荐

评论

题解：P12543 嘟嘟嘟