Arithmetic Progression CodeForces - 382C

2021/7/18 23:13:05

本文主要是介绍Arithmetic Progression CodeForces - 382C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接
考察:模拟(?)
思路:
  分类讨论就完事.
(1) \(n=1\)
(2) \(n=2\),这里一定要分\(d = 0\)的情况.
(3) \(n>2\),这里一定要注意\(cnt = 0\)的情况,此时合法的情况是只有两种公差,且大公差一定是小公差的\(2\)倍.

Code

#include <iostream> 
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 100010;
int n,a[N],b[N];
void solve()
{
	if(n==1) {puts("-1");return ;} 
	if(n==2)
	{
		int c = a[2]-a[1];
		if(c%2)
			printf("2\n%d %d\n",a[1]-c,a[2]+c);
		else if(c)
		    printf("3\n%d %d %d\n",a[1]-c,a[1]+c/2,a[2]+c);
		else
		    printf("1\n%d\n",a[1]);
		return;
	}
	map<int,int> mp;
	for(int i=1;i<n;i++)
	{
		b[i] = a[i+1]-a[i];
		mp[b[i]]++;
	}
	if(mp.size()>2) {puts("0"); return ;} 
	if(mp.size()==1)
	{
		if(!b[1]) printf("1\n%d\n",a[1]);
		else printf("2\n%d %d\n",a[1]-b[1],a[n]+b[1]);
		return;
	}
	sort(b+1,b+n);
	if(mp[b[1]]>1&&mp[b[n-1]]>1) puts("0");
	else if(mp[b[1]]<mp[b[n-1]]) puts("0");
	else if(b[n-1]%2||b[n-1]/2!=b[1]) puts("0");
	else {
		for(int i=1;i<n;i++)
		  if(a[i+1]-a[i]==b[n-1])
		  {
		  	printf("1\n%d\n",a[i]+b[n-1]/2);
		  	break;
		  }
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	solve();
	return 0;
}


这篇关于Arithmetic Progression CodeForces - 382C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程