P8297 [COCI2012-2013#2] LANCI

宇宙安全声明：本题解采取感谢证明+理性理解方式讲解，包含若干手模。

题面：

P8297

感性证明：

先模拟下样例二：

打开 3 最右边一节，连接 5 和 7；

打开 3-1 最右边一节，连接 4 和 9；

打开 3-1-1 最后一节，连接 5+7 和 4+9。

大概思想就是：找一条链，一节一节取，连接两个，计算一次。

但也有问题，比如样例：

5
4 3 5 7 9

我们用 4 的话，答案会变为 4，因为最后 4 没有变成单点，而是变成了一条链，需要两次才能连接。

这也说明要选择较小的链来拆。然后考虑如果拆完不够，是否会出现问题。

5
4 2 5 7 9

用 2 拆完，还剩下有两条链，不过答案仍为 3。

5
4 1 5 7 9

用 1 拆完，则剩下三条链，这时暴力连接和拆链连接答案均为 3，不用 1 答案也为 3。

6
4 1 5 7 9 6

用 1 拆完，会剩下四条链，此时暴力和拆链答案均为 4，不用 1 答案也为 4。

瞪眼法发现可以拆开最短链，用单点连接最长的两条，拆完后暴力连接即可。

但是没考虑过多条等长链，于是再模一下：

5
1 1 2 3 4

一个 1 连接完剩下 3 条，剩下一个 1 再连一次结束，答案为 2，naive 了。

这个属于单点没用合理。

递归思考一下：

第一层：1 1 2 3 4，选择 1 最短，记录答案为 1，进入第二层统计并返回。

第二层：1 2 7 ，选择 1 最短，记录答案为 1，结束并返回

发现可以拆成子问题，每一次选取最短的链拆分。

理性理解：

其实拆链和暴力是一样的，都是一个节点连接了两条链，并且顺序不会影响答案。

但是拆链最后可能吃到单点的优化，暴力不行。

又由于要拆成单点，所以尽量选短的来拆，自然只能增加长链来减少影响。

所以理性理解可以发现上述感性证明是正确的！

实现细节：

1. 为了方便找最长最短，要先排序，然后递归或者循环双指针。
2. 单链不一定能拆完，所以不能直接加上对应的长度。
3. 注意两个指针的边界。

Code：

//递归版
#include<bits/stdc++.h>
using namespace std;
template<typename Type>
inline void read(Type& x){
	x=0;bool flag=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
	if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)-(ch&15);
	else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
}
template<typename ...Args>
inline void read(Args& ...args){
	int a[]{(read(args),0)...};
}
inline void _fre(string txt){
	freopen((txt+".in").c_str(),"r",stdin);
	freopen((txt+".out").c_str(),"w",stdout);
}
const int N=500005;
int n;
int L[N],used=1000000;
int dfs(int l,int r){
	if(l>=r) return 0;
	int ret=0;
	while(L[l]&&l<r) L[r-1]+=L[r],L[l]--,r--,++ret;
	return ret+dfs(l+1,r);
}
signed main(){
	read(n);
	for(int i=1;i<=n;++i) read(L[i]);
	sort(L+1,L+n+1);
	printf("%d",dfs(1,n));
	return 0;
}

//双指针版
#include<bits/stdc++.h>
using namespace std;
template<typename Type>
inline void read(Type& x){
	x=0;bool flag=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
	if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)-(ch&15);
	else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
}
template<typename ...Args>
inline void read(Args& ...args){
	int a[]{(read(args),0)...};
}
const int N=500005;
int n;
int L[N];
signed main(){
	read(n);
	for(int i=1;i<=n;++i) read(L[i]);
	sort(L+1,L+n+1);
	int ans=0;
	for(int l=1,r=n;l<r;l++){
		while(L[l]&&l<r) L[r-1]+=L[r]+1,L[l]--,r--,++ans;
	}
	printf("%d",ans);
	return 0;
}

Ps:本题解大部分是校内模拟赛期间写完的，可能有些地方看起来有点奇怪，见谅。