【日常小测】仰望星空

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

我们按照极角序来贪心匹配
不难发现这样一定有解

另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
	int x, y, ty;
	inline int dis(const Point &P) {
		return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
	}
}p[N];

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
} 

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool DFS(int w) {
	vis[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
			mth[to[i]] = w;
			mth[w] = to[i];
			return 1;
		} 
	}
	return 0;
}

inline int solve() {
	int ret = 0;
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (!mth[i]) {
			memset(vis, 0, sizeof(vis));
			ret += DFS(i);
		}
	}
	return ret;
}

inline void print(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] == mth[w]) {
			vis[w] = vis[to[i]] = 1;
			printf("%d %d\n", w, mth[w]);
			return;
		} else if (!vis[to[i]]){
			print(mth[to[i]]);
		}
	}
}

int main() {
	n = read(); 
	R = read(); R *= R;
	D = read(); D *= D;
	S = 0; T = N - 1;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (p[i].ty = p[i].dis(p[1]) > R) {
			in[++cnt_in] = i;
		} else {
			ot[++cnt_ot] = i;
		}
	}
	for (int ii = 1; ii <= cnt_in; ii++) {
		int i = in[ii], cnt_arr = 0;
		double mx = -PI, mn = PI;
		for (int jj = 1; jj <= cnt_ot; jj++) {
			int j = ot[jj];
			if (p[i].dis(p[j]) <= D) {
				double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
				mx = max(mx, agl);
				mn = min(mn, agl);
				arr[++cnt_arr] = make_pair(agl, j);
			}
		}
		if (mx - mn >= PI) {
			for (int j = 1; j <= cnt_arr; j++) {
				arr[j].first += arr[j].first < 0? PI * 2: 0;
			}
		}
		sort(arr + 1, arr + 1 + cnt_arr);
		for (int j = 1; j <= cnt_arr; j++) {
			AddEdge(i, arr[j].second);
		}
	}
	printf("%d\n", solve() << 1);
	memset(vis, 0, sizeof(vis));
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (mth[i] && !vis[i]) {
			print(i);
		}
	}
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL ans;
  
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
  
int find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【TopCoder SRM714】Salesman

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14120&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358439

解题报告

设最终移动的范围为$[l,r]$
那么如果存在$r’ < r$且$sum_{l \to r’} \ge 0$,则$r’$优于$r$
所以我们可以枚举左端点,然后找到其对应的最优右端点

接下来就是区间内的路径规划问题
我们可以假设先走到左端点,那么剩下的东西的分配一定是尽量往左分配
这样就可以贪心了

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 1e9;
const int N = 1e4;

int pfx[N],delta[N],pos[N],nxt[N];

class Salesman {
    public:
    	int minMoves(vector<int> ppos, vector<int> ddelta) {
    	    int n = ppos.size();
    	    for (int i=1;i<=n;i++) {
				pos[i] = ppos[i - 1];
				delta[i] = ddelta[i - 1];
			}
			int ans = INF;
			ans = min(ans, solve(n));
			for (int l=1,r=n;l<r;l++,r--) {
				swap(pos[l], pos[r]);
				swap(delta[l], delta[r]);
			}
			for (int i=1;i<=n;i++) {
				pos[i] = -pos[i];
			}
			ans = min(ans, solve(n));
			return ans;
   		}
   	private:
   		inline int solve(int n) {
			int mn = INF, mx = -INF, ret = INF;
			for (int i=1;i<=n;i++) {
				pfx[i] = pfx[i-1] + delta[i];
				if (delta[i] < 0) {
					mx = max(mx, i);
					mn = min(mn, i);
				}
			}   
			for (int i=n,j=n;i;i--) {
				if (delta[i] < 0) {
					j = i;
				}
				nxt[i] = j;
			}
			if (mn == INF) {
				return 0;
			}
			for (int l=1;l<=mn;l++) {
				for (int r=mx;r<=n;r++) {
					if (pfx[r] - pfx[l - 1] >= 0) {
						ret = min(ret, cal(l, r));	
						break;
					}
				}
			}
			return ret;
		}
		inline int cal(int l, int r) {
			int ret = pos[r] - pos[l] + abs(pos[l]), ans = INF;
			int cry = 0, ned = 0, ptn = 0;
			for (int i=l;i<=r;i++) {
				if (delta[i] >= 0) {
					cry += delta[i];
					if (cry >= ned && ned) {
						cry -= ned;
						ret += max(0, pos[i] - ptn) << 1;
						ned = 0;
					}
				} else if (delta[i] < 0) {
					if (!ned && cry >= -delta[i]) {
						cry += delta[i];
					} else {
						if (!ned) {
							ptn = max(ptn, pos[i]);
						} 
						ned -= delta[i];
					}
				}
				
				ans = min(ans, ret + max(0, pos[r] - (ned? ptn: pos[nxt[i+1]])));
			}
			return ans;
		}
};

【LA 5524】[EC2015 Final] Suffixes and Palindromes

相关链接

题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5524

题目大意

给出一个串的$sa$数组和$manacher$求出的那个数组
请你构造出一个字典序最小的符合条件的串,可能无解

有$T(T \le 100)$组数据
数组长度$\le 10^5$
时间限制:$4s$

背景

Claris给我安利的题,似乎子问题都会的样子
但合起来就不会了

解题报告

考虑$manacher$的那个数组,实际上是给出了$O(n)$条信息
每一条信息形如:第$i$个字符(不)等于第$j$个字符
如果只有这个条件的话,我们可以搞成几个大连通块,然后贪心

考虑$sa$数组,上午才做了这个题
也可以直接贪心

但这两货直接合在一起,似乎是给出一个差分约束系统
然后让你输出一组可行解,还要让你字典序最小
于是就不会了

但我们还是考虑直接在$SA$数组上贪心
考虑回文等价的影响的话,那实际上是填一位就会影响后面的很多位
似乎想一想,直接贪心会不会使一个区间的两头被值域给卡住
但仔细想一想,即使你给那一个等价类一个大一点的字符,区间的差分序列没有变啊
该卡住的还是会卡住,没被卡住的也不会有问题

于是我们任然在SA数组上贪心,考虑能不能与前一个数相等的时候
不仅考虑$rank$数组的影响,我们还需要考虑回文等价的影响
于是这题就这么做完啦,仍然是一个$O(n)$的贪心

【BZOJ 4319】[CERC2008] Suffix Reconstruction

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4319
神犇题解:http://www.cnblogs.com/Skyminer/p/6414088.html

解题报告

之前在做这个题的时候就听说过这题
但当时想了一会儿,感觉不可做,以为是他们记错题目了 QwQ
今天居然看到原题了,但想了很久,还是只会$O(26 \cdot n \log{n})$

先来说说$O(26 \cdot n \log{n})$的做法吧!
我们可以从上到下单个字符填,就是尽量往小的填,填完以后$O(n)$验证一遍

我们考虑分出不同的地方,因为填了都是比他小的,所以如果冲突,那一定是之前的太大了
但之前的部分已经贪心尽量小地填了,所以之前的肯定不能改小了,只能把当前位改大

所以这么做是对的,时间复杂度:$O(26 \cdot n^2)$
不难发现$SA$数组上一定是一段连续的A,之后一段连续的B。后面也是这样
于是我们可以二分每一个字符地分界点,这样复杂度就是$O(26 \cdot n \log{n})$的了

正解的话,是$O(n)$的,仍然是从小到大贪心
我们考虑计算$height$数组时候那个Trick的正确性证明
如果$rank[sa[i]+1] > rank[sa[i+1]+1]$的话,那么$sa[i]$填的字符一定比$sa[i+1]$小
否则他俩相等也没有关系,因为后面还是会把他们区分出来
于是贪心就可以$O(1)$验证了,于是总的时间复杂度就是线性的了!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;

int n,sa[N],rak[N];
char ans[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); 
	for (int i=1;i<=n;i++) rak[sa[i]=read()]=i;
	ans[sa[1]] = 'a';
	for (int i=1,w='a';i<n;i++) (rak[sa[i]+1]>rak[sa[i+1]+1])? ans[sa[i+1]]=++w: ans[sa[i+1]]=w;
	if (ans[n] <= 'z') printf("%s",ans+1);
	else puts("-1");
	return 0;
}

【BZOJ 4700】适者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4700
神犇题解:http://blog.csdn.net/werkeytom_ftd/article/details/54565251

解题报告

设第$i$个机器人打$t_i$次就会$GG$,攻击力是$v_i$
那么推推式子发现$i$比$j$先死更优,当且仅当$t_iv_j < t_jv_i$
于是我们先排个序,贪一贪心

现在考虑如何一开始就$GG$掉的两个,因为删除之后不会影响决策
所以我们相当于在贪心后的删除序列上再删掉两个点
考虑删掉的第一个点对于第二个点的贡献,形如$av_i+b$
这是一个直线的表达式,于是相当于让你维护一个数据结构,支持插入直线、查询单点最值
这个是一个经典的数据结构问题,可以用李超树来解决
总时间复杂度:$O(n \log n)$

另外,这题还有CDQ分治的做法,时间复杂度仍然为$O(n \log n)$
再另外,我居然暂时是$Rank \ 1$!第一次$Rank \ 1$啊! ★,°:.☆( ̄▽ ̄)/$:.°★

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int INF = 10000;
const double EPS = 1e-6;

int n,ATK; LL sum[N],pre[N],vout,ans;
struct ROB{int t,v;}r[N];
inline bool cmp(const ROB &A, const ROB &B) {return (LL)A.t * B.v < (LL)B.t * A.v;} 

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

class Segment_Tree{
	int root,cnt; LL AnsTmp;
	struct Node{int ch[2],a; LL b,pl,pr;double pm;}p[N<<1];
	public:
		inline void insert(int a, LL b) {
			insert(root, 1, INF, a, b);
		}
		inline LL query(int x) {
			AnsTmp = 0;
			query(root, 1, INF, x);
			return AnsTmp;
		}
	private:
		void insert(int &w, int l, int r, int a, LL b) {
			if (!w) w = ++cnt;
			if (!p[w].a) {p[w].a = a, p[w].b = b; return;}
			LL nl = (LL)a*l+b, nr = (LL)a*r+b; 
			double nm=(l+r)*0.5*a+b; int mid=l+r+1>>1;
			if (nl <= p[w].pl && nr <= p[w].pr) return;
			if (nm > p[w].pm) {
				if (nl < p[w].pl || nr < p[w].pr) {
					if (nl < p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, p[w].a, p[w].b);
					if (nr < p[w].pr && l < r) insert(p[w].ch[1], mid, r, p[w].a, p[w].b);
				} p[w].a = a; p[w].b = b; p[w].pl = nl; p[w].pr = nr; p[w].pm = nm;
			} else {
				if (nl > p[w].pl && l < r) insert(p[w].ch[0], l, mid-1, a, b);
				if (nr > p[w].pr && l < r) insert(p[w].ch[1], mid, r, a, b);
			}
 		}
		void query(int w, int l, int r, int pos) {
			if (!w) return;
			if (p[w].a) AnsTmp = max(AnsTmp, (LL)p[w].a * pos + p[w].b);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (pos < mid) query(p[w].ch[0], l, mid-1, pos);
				else query(p[w].ch[1], mid, r, pos);
			}
		}
}SGT;

int main() {
	n = read(); ATK = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		b = ceil((double)b / ATK) + EPS;
		r[i].v = a; r[i].t = b;
	}
	sort(r+1, r+1+n, cmp);
	for (int i=1;i<=n;i++) pre[i] = pre[i-1] + r[i].t;
	for (int i=n;i;i--) sum[i] = sum[i+1] + r[i].v;
	for (int i=1;i<=n;i++) {
		LL tmp = SGT.query(r[i].v);
		LL nv = sum[i]*r[i].t-r[i].v+pre[i-1]*r[i].v; 
		if (i > 1) vout = max(vout, tmp + nv);
		SGT.insert(-r[i].t, nv);
	}
	for (int i=1;i<=n;i++) ans += (pre[i] - 1) * r[i].v; 
	printf("%lld\n",ans-vout);
	return 0;
}

【日常小测】苹果和雪梨

题目大意

给你$n(n \le 3000)$个梨,$n$个苹果。每个梨有个权值$a_i$,每个苹果有个权值$b_i$
现在让你求出一种匹配关系,使得梨与苹果一一配对,使得获益最大。
设$i$号梨对应$f_i$号苹果,定义收益为$\sum\limits_{i=1}^{n}{a_i \cdot b_{f_i}}-\max\{a_i \cdot b_{f_i}\}$

解题报告

这题有一个非常显然的$O(n^4)$的暴力:

$O(n^2)$枚举最大值是哪一对
对于其他梨,贪心选择最大的、可以选的苹果配对

这种暴力优化一下,据说可以优化到$O(n^3)$

但我们仔细想一想,这种XJB枚举最大值很不优雅,会做很多重复的动作
于是我们考虑从小到大枚举最大值是哪一对
考虑我们此时将涉及到的四个点更改匹配关系即可
时间复杂度:$O(n^2 \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 3009;
const int M = N * N;

LL n,tot,vout,ans,mx,a[N],b[N],p[N],q[N]; 
struct Match{int x,y;LL val;}m[M];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) a[i] = read();
	for (int j=1;j<=n;j++) b[j] = read();
	sort(a+1, a+1+n); sort(b+1, b+1+n);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			m[++tot].val = a[i] * b[j];	
			m[tot].x = i; m[tot].y = j;
		}
	}
	static auto cmp = [](const Match &A, const Match &B) {return A.val < B.val || (A.val == B.val && A.x < B.x) || (A.val == B.val && A.x == B.x && A.y < B.y);};
	sort(m+1, m+1+tot, cmp);
	for (int i=1;i<=n;i++) 
		mx = max(mx, a[i] * b[n-i+1]);
	for (int i=n;i;i--) {
		for (int j=n;j;j--) {
			if (!q[j] && a[i] * b[j] <= mx) {
				q[j] = i; p[i] = j;
				ans += a[i] * b[j];
				break;
			}
		}
	}
	vout = ans - mx;
	for (int i=1,x,y,nx,ny;i<=tot;i++) {
		if (m[i].val <= mx) continue;
		x = m[i].x; y = m[i].y; nx = p[x]; ny = q[y];
		p[ny] = nx; q[nx] = ny; p[x] = y; q[y] = x;
		ans += a[x] * b[y] + a[ny] * b[nx];
		ans -= a[x] * b[nx] + a[ny] * b[y];
		vout = max(vout, ans - m[i].val);
	}
	printf("%lld\n",vout);
	return 0;
}

【TopCoder】[TCO2013 2C] Well Timed Search

相关链接

题目传送门:https://arena.topcoder.com/#/u/practiceCode/15657/31723/12515/1/317358
中文题面及题解:http://picks.logdown.com/posts/208980-solutions-to-topcoder-open-2013s-hard-problems

解题报告

这题从头到尾都只会 $O(n^3)$ 的 $DP$
想了四个小时啊 QwQ

考虑搞出一个二叉搜索树
显然我们可以控制一个节点的左右儿子有多少个
因为我们可以询问当前区间的端点,所以我们还可以控制有没有左右儿子
换一句话说,我们可以钦定这棵搜索树的形态

我们继续观察可以发现一下两条:

  1. 我们可以根据一个节点左右儿子子树的大小,求得往左、往右走的概率
  2. 每一个深度在$[A,B]$的节点都是一个合法的结束

于是我们就可以枚举第$A$层有多少结点,然后贪心往下放就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

class WellTimedSearch {
    public:
	double getProbability(int n, int A, int B) {
		int vout = 0; 
		for (int i=1,up,down;i<=n;i++) {
			if (A > 1) up = Get_Top(i+1>>1, A-1);
			else {if (i == 1) up = 0; else up = 1e9;}
			if (n - up - i < 0) break;
			down = Get_Down(B-A, n - up - i, i<<1);
			vout = max(vout, i + down);
		}
		return (double)vout / n;
	}
   	private:
	int Get_Top(int len, int t) {
		if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
		if (t == 1 && len > 1) return 1e9;
		return 1;
	}
	int Get_Down(int t, int num_node, int cur) {
		if (!t) return 0;
		if (cur >= num_node) return num_node;
		return cur + Get_Down(t-1, num_node - cur, cur<<1);
	}
};

【UVa 11134】Fabled Rooks

题目传送门:https://uva.onlinejudge.org/external/111/11134.pdf
中文题面:《算法竞赛·入门经典·训练指南》P81

首先这题的行列无关,所以肯定可以分开考虑
于是就转化为了一维的情况

之后的事情,貌似网络流+线段树结构优化建图也能A?
我人懒,写的贪心 QAQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000+9;

int xl[N],xr[N],yr[N],yl[N],X[N],Y[N],n;
deque<pair<int,int> > beg[N]; deque<int> End[N];
priority_queue<pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > > que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline bool solve(int *l, int *r, int *ret) {
	memset(ret,0,sizeof(X));
	while (!que.empty()) que.pop();
	for (int i=1;i<=n;i++) {
		beg[i].clear(); 
		End[i].clear();
	}
	for (int i=1;i<=n;i++) {
		beg[l[i]].push_back(make_pair(r[i],i));
		End[r[i]].push_back(i);
	}
	
	for (int i=1;i<=n;i++) {
		while (!beg[i].empty()) {
			pair<int,int> w = beg[i].front(); 
			beg[i].pop_front();
			que.push(make_pair(w.first,w.second));
		}
		
		if (que.empty()) return false;
		ret[que.top().second] = i;
		que.pop();
		
		while (!End[i].empty()) {
			if (!ret[End[i].front()]) 
				return false;
			End[i].pop_front();
		}
	}
	return true;
}

int main(){
	for (n=read();n;n=read()) {
		for (int i=1;i<=n;i++) {
			xl[i] = read(); yl[i] = read();
			xr[i] = read();	yr[i] = read();
		}
		
		if (!solve(xl,xr,X)) {puts("IMPOSSIBLE"); continue;}
		if (!solve(yl,yr,Y)) {puts("IMPOSSIBLE"); continue;}
		
		for (int i=1;i<=n;i++) 
			printf("%d %d\n",X[i],Y[i]);
	}
	return 0;
}

【POJ 3514】[NEERC2006] Graveyard

题目传送门:http://poj.org/problem?id=3154
中文题面:《算法竞赛·入门经典·训练指南》P7

作为一道很有趣的贪心,我居然只会O(n^2)的DP
真是惭愧……..
下面说正经事:

引理一:

一定存在一种最优方案,使得至少有一个最终的雕塑位置与原位置重叠

证明:

考虑每一个原的雕塑位置
设最近的最终雕塑位置在顺时针方向的点集为A
设最近的最终雕塑位置在逆时针方向的点集为A
1)|A|==|B|:显然将距离最终雕塑位置最小的点移动过去不会使答案变劣
2)|A|<|B|:显然逆时针转动尽量小的距离,使得有一个原雕塑与最终雕塑位置重叠会使答案变优
3)|A|>|B|:同理可得:应顺时针转动最小距离

引理二:

不会有两个原雕塑位置离同一个最终雕塑位置最近

证明:

设原雕塑间隔为A,最终的雕塑间隔为B
若两个原雕塑位置离同一个最终雕塑位置最近,则这两个原雕塑间的距离小于B(类比四舍五入)
但由题意得:A < B
矛盾,所以这种情况不可能发生

证明了这两个引理之后,就可以贪心啦!
随便定一个点,然后将每个原雕塑位置移动到最近的最终雕塑位置即可