CF1864A Increasing and Decreasing

发布时间 2023-08-29 11:03:25作者: One_JuRuo

思路

首先,给定了一个序列的首项 \(a_1\) 和末项 \(a_n\) 以及项数 \(n\),要求构造一个严格递增,且差严格递减的序列。

因为是构造题,所以可以随便造,考虑差严格递减,所以从后往前构造比较合理。

因为严格递增,所以差至少为 \(1\),所以 \(a_{n-1}\) 就构造成 \(a_n-1\)\(a_{n-2}\) 就构造成 \(n_{a-1}-2\),以此类推。

那么什么时候无解呢?因为差至少也得是 \(1,2,3\cdots n-1\),所以当 \(a_1+\frac {n\times(n-1)}2>a_n\) 时,代表无法构造。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[1005],cnt,b;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&a[1],&b),scanf("%d",&n),a[n]=b,cnt=1;
		if(a[1]+(n-1)*n/2>b){printf("-1\n");continue;}
		for(int i=n-1;i>1;--i)
		{
			a[i]=a[i+1]-cnt,++cnt;
		}
		for(int i=1;i<=n;++i) printf("%d ",a[i]);
		puts("");
	}
	return 0;
}