哈，乌鸦
淘宝杜琨
这个题目我说说自己的想法和证明,如果有错,请大家指出,
对于输入数据 (4,2,2,1,1)
该图可以这么构造:
因为第一个点的数字为4那么它肯定和后面的点中4个相连
现在从图中去掉该点和对应的边,残量图也对应一个度序列:(0,1,1,0,0)
我们可以按照这个方法对残量图进行继续重复操作,直到残量图为(0,0,0,0,0)如果能够达到这样的结果,者对应的图肯定存在否则不存在.
但是现在出现一个问题:
构造残量图的方法不是唯一的:
比如 (2,2,2,1,1)消掉第一个点后可能的残量图度序列有:
(0,1,1,1,1);(0,1,2,0,1)等等等等,这些不同的构造路径中只要有一个成功,显然结果就是Yes.
想到这里我想到了搜索,但是很显然搜索的规模很大,而且楼主没给出数据范围,我猜想数据范围是可以很大的,于是开始想其它办法.
这时候我想到了残量图的构造过程,如果剩下 (3,2,0,0)这种是肯定不行了,那么不行的原因是3和2不同,从大体上来说可以这么猜想:该图的度序列如果波动越小,那么构造成功的可能性越大.
由此猜想出一个贪心算法:
对于每个图,
消去度最大的那个点,消去的方法假设度最大的点分别与度第二大,度第三大,...度第N大的点连有边(N刚好满足把该点的度消为0),如此消去该图,一直这么操作,如果可以把所有的点的度都消为0,就YES,否则NO;
对该算法的证明:
证明的目标是:对于任意一个从大到小排列的度序列(a1,a2,a3,a4..an),现在要消去其中度最大的一个点,对于消法A:有一个对应的效法B满足,B和A中要减掉的点只有一个不同,A为x变为x-1,B为y变为y-1(x>y)
例如对于(3,2,2,1,1)消2,
A方按:(2-2,2-1,2-1,1-1,1);
B方按:(2-2,2-1,2,1-1,1-1);只有2-1,与1-1一项不同.
显然A方按的结果为(.....,x-1,y);B方按的结果为(......,x,y-1)前面为相同部分如果B方案操作后有满足条件的图G,那么因为x>y所以,x>(y-1),如此肯定G中存在一个点,它只与x对应的点相连而不与(y-1)对应的点相连,把该点与x对应的点的边去掉,再加上一条该边与(y-1)相连的边,得到的新图对应的度序列为(.....,x-1,y)!!!!!
由此可知B方案可行A方案就一定可行,即A方案比B方案更"优".将各种可能的方案列出,显然贪心方案是最"优"的，因为如果它是B方案,找不出和它对应的A方案,故贪心算法是正确的
下面是代码,算法复杂度为O(N^2),考虑空间问题我采用了两次检查(第一次检查,第二次输出)的方法,空间复杂度为O(N);如果一次检查过程并记录的话空间复杂度为O(N^2),因为根据时间复杂度,N可以高达100000,故选择前者保证足够的空间:
#include <stdio.h>
#include <string.h>
FILE *fi,*fo;
#define DMAX 1000
long data[DMAX],n,p[DMAX];
long tmp_data[DMAX],tmp_p[DMAX];
long part(long l,long r)
{/*间接对p[]:记录data的下标的数组,进行从大到小排序*/
long tmp,key=data[p[(l+r)>>1]];
while(1){
while(data[p[l]]>key)
++l;
while(data[p[r]]<key)
--r;
if(l>=r) return r;
tmp=p[l];p[l]=p[r];p[r]=tmp;
++l;--r;
}
}
void q_sort(long l,long r)
{/*快排*/
long mid;
if(l>=r) return;
mid=part(l,r);
q_sort(l,mid);
q_sort(mid+1,r);
}
void init()
{/*数据初始化 */
long i;
for(i=0;i<n;i++){
fscanf(fi,"%ld",&data[i]);p[i]=i;
}
q_sort(0,n-1);
memcpy(tmp_data,data,sizeof(data));
memcpy(tmp_p,p,sizeof(p));
}
void resort(long begin,long end)
{/*从新将新序列排序*/
long i,j,tmp;
for(i=end;i>begin;i--){
for(j=i+1;j<n&&data[p[j-1]]<data[p[j]];j++){
tmp=p[j-1];p[j-1]=p[j];p[j]=tmp;
}
}
}
int ok(unsigned char print)
{/*检查并且打印,print决定是否边检查边输出*/
long i,j,jmax;
for(i=0;i<n;i++){
jmax=i+data[p[i]];
if(jmax>=n) return 0;
for(j=i+1;j<=jmax;j++)
if(!data[p[j]]) return 0;
else {
data[p[j]]--;
if(print) fprintf(fo,"%ld %ld\n",p[i]+1,p[j]+1);
}
resort(i,jmax);
}
return 1;
}
int main(void)
{
//fi=stdin; /*选择键盘输入方式*/
fi=fopen("input.txt","r");
//fo=fopen("ouput.txt","w");/*选择文件输出方式*/
fo=stdout;
while(fscanf(fi,"%ld",&n)==1){
init();
if(ok(0)){
fprintf(fo,"Yes!\n");
memcpy(data,tmp_data,sizeof(data));
memcpy(p,tmp_p,sizeof(p));
ok(1);
}
else fprintf(fo,"No!\n");
}
getch();/*文件输出的时候这个应该去掉*/
fclose(fi);
//fclose(fo);
return 0;
}
PS:我有些怀疑这是否是OI的题目,因为一般OI的题目输出都是确定的,但是这个题目对于一个输入似乎可以有多种输出,或许是题目条件漏了或者我多虑了吧,也可能是我的思路不对,请大家评判
