Codeforces Round 887 (Div. 2)

A. Desorting

题意：给出一个数组，可以进行任意次以下操作：

选择一个i

对于数组中的a[1],a[2],...,a[i]全部+1

a[i+1]...a[n]全部-1,

问最小使得数组变得无序的操作是多少次

Solution

直接找相邻的两个数的最小的差值即可

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int res=INF;
	for(int i=1;i<n;i++)res=min(a[i+1]-a[i],res);
	if(res<0)
	{
		cout<<"0\n";
	}else
	{
		if(res&1)
		{
			cout<<(res+1)/2<<"\n";
		}else cout<<res/2+1<<"\n";
	}
}

B. Fibonaccharsis

题意：给出n，k，问有多少对x,y(x<=y)，使得n是以这两个数为a[1],a[2]的斐波那契数列的第k个数

Solution

对于第k个数我们可以预处理出来它是由x[k]个a[1]和y[k]个a[2]组成的，由于a[1]<=a[2]，这样我们可以得到a[1]的上限

我们找到第一个满足的最小的a[1]，然后每次往后可以加上lcm(x[k],y[k])个a[1]，以此保证最小

void solve()
{
	int n,k;cin>>n>>k;
	if(k>pos)
	{
		cout<<"0\n";
		return;
	}
	if(n<x[k]&&n<y[k])
	{
		cout<<"0\n";
		return;
	}
	int ans=0;
	int l=0,r=0;
	int lmax=n/(x[k]+y[k]);
	
	//cout<<lmax<<"\n";
	while(n>0&&n%y[k]!=0)
	{
		n-=x[k];
		l++;
		
	}
	r=n/y[k];
	ans++;
	if(l>r)
	{
		cout<<"0\n";
		return;
	}
	int z=lcm(x[k],y[k]);
	
	
	//cout<<z/x[k]<<"\n";
	ans+=(lmax-l)/(z/x[k]);
	cout<<ans<<"\n";
	
}

C. Ntarsis' Set

题意：给出n，k，和一个长为n的数组a，有一个集合，包含了从1到10¹⁰⁰⁰,每一轮删除掉第a[1],a[2],...,a[n]个数，问最后剩下的数里面最小是多少

Solution

模拟一遍删除的过程，我们来看这样一个图

我们考虑每一个位置应该删掉哪些数，对于1到x之间的，只会由1来删除，1每次删除的位置都会+1，很容易理解，而对于x到y之间的，会由1和x删除，而x每次删除的位置都会+2，因为对于每一个x到y之间的数来说，他们的位置都在-2，要想删除第x个数，每次都必须+2，同理y到z之间的数每次y都会删除y+3的位置的数

也就是会呈现以下的情况

可能根据x，y之间的数量不同，呈现的结果也不同，但是归根到底，我们可以发现，每跨越一个a[i]，需要删除的下一个位置的距离就会+1，假设第k次删除的位置是pos，下一次跨越需要dis，那么很显然答案就是pos+dis

void solve()
{
	int n,k;cin>>n>>k;
	set<int>st;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		
	}
	if(a[1]!=1)
	{
		cout<<"1\n";
		return;
	}
	int num=0;
	
	int pos=1;
	int cnt=0;
	int nex=0;
	while(cnt!=k)
	{
		while(nex+1<=n&&pos+nex>=a[nex+1])
		{
			nex++;
		}
		pos+=nex;
		cnt++;
		//cout<<pos<<" ";
	}
	cout<<pos<<"\n";
}

D. Imbalanced Arrays

题意：给出一个数组a，构造一个数组b，使得对于每一个i，有a[i]个j满足b[i]+b[j]>0，并且不存在b[i]+b[j]=0，0<=a[i]<=n,-n<=b[i]<=n

Solution

首先a[i]越大，b[i]越大

将a排序一下，两边从n开始构造

这样保证构造b[l]时能小于所有b[r+1,...n]的情况下，并且构造b[r]时，b[l,l+1,...,n]都小于等于b[r]

如果当前能满足构造的需求的话则可以，如果都无法满足的话则无法完成构造

struct node
{
	int x,y;
	bool operator < (const node&t)const &{
		if(x!=t.x)return x<t.x;
		else return y<t.y;
	}
}b[N];
int c[N];
int ans[N];
 
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i].x=a[i];
		b[i].y=i;
	}
	sort(b+1,b+1+n);
	//for(int i=1;i<=n;i++)cout<<b[i].x<<" \n"[i==n];
	
	int pos=n;
	int l=1,r=n;
	while(l<=r)
	{
		if(b[l].x==n-r)
		{
			ans[b[l++].y]=-(pos--);
			continue;
		}
		if(b[r].x==n-l+1)
		{
			ans[b[r--].y]=pos--;
			continue;
		}
		cout<<"NO\n";
		return;
	}
	cout<<"YES\n";
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<" \n"[i==n];
	}
}