博客

寻找一个有n个整数的数列，满足下列条件：

其中任意连续p个数之和是正数。

其中任意连续q个数之和是负数。

若无法找到，则输出”No”，否则输出一个数值最小的数列。

输入  n  p  q

输出  n个整数

样例：

输入：

5 4 3

输出：

2 2 -5 2 2

设： si——数列前i个数之和。

所以有

s[i]=a[1]+a[2]+…+a[i]

s[0]=0;

s[i+p]-s[i]>0 s[i+p]>s[i]

s[i+q]-s[i]<0 s[i+q]<s[i]

构图：

点——i (0..n)

权——s[i]

边——当s[i]>s[j]时 有(i,j)

如n,p,q=6,5,3

s[i]>s[i+3]

s[i+5]>s[i]

拓扑号： 0 1 2 3   4   5  6

2 5 0 3   6   1  4

↑ 这个我们知道。  而要最小、 所以往前一次递增，往后依次递减。

s[i]  ： 2 1

0

-1 -2 -3  -4

a[i]=s[i]-s[i-1]: 1  2  3  4  5  6

-3 5 -3 -3  5 -3

#include


<


stdio.h


>



#include


<


stdlib.h


>





int


n,p,q,i,j,k,g[


100


][


100


],ID[


100


],s[


100


],a[


100


];



int


main(){


freopen(


”


寻找队列.in


”


,


”


r


”


,stdin);

freopen(


”


寻找队列.out


”


,


”


w


”


,stdout);

scanf(


”


%d%d%d


”


,


&


n,


&


p,


&


q);



for


(i


=


0


;i


<=


n


–


p;i


++


){


g[i


+


p][i]


=


1


;

ID[i]


++


;

}



for


(i


=


0


;i


<=


n


–


q;i


++


){


g[i][i


+


q]


=


1


;

ID[i


+


q]


++


;

}

i


=-


1


;



do


{


i


++


; j


=


0


;



while


(j


<=


n


&&


ID[j]


!=


0


) j


++


;



if


(j


<=


n){


s[i]


=


j; ID[j]


=


2147483647


;

a[j]


=


i;



for


(k


=


0


;k


<=


n;k


++


)



if


(g[j][k]


==


1


) ID[k]


—


;

}

}


while


(j


<=


n


&&


i


!=


n);



if


(i


<


n){


printf(


”


No\n


”


);



return




0


;

}

for


(i


=


0


;i


<


n;i


++


)

printf(


”


%d


”


,a[i]


–


a[i


+


1


]);



return




0


;

}