寻找一个有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
![](https://images.cnblogs.com/cnblogs_com/yanrui7098/xzsl.jpg)
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
Code
#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;
}