Codeforces Round #813 (Div. 2)

A. Wonderful Permutation

题目链接：Problem - A - Codeforces

样例输入：

4
3 1
2 3 1
3 3
1 2 3
4 2
3 4 1 2
1 1
1

样例输出：

1
0
2
0

题意：初始给定一个长度为n的1~n的排列，然后我们可以对其进行操作，每次操作可以选择两个位置的数并进行交换，问至少需要操作多少次可以使得前k个位置是1~k的排列。

分析：很容易得到一个结论就是如果前k个位置上有大于k的数那么我们就需要将其换出去，并换进来一个小于等于k的数，那么答案显然就是初始排列中位于1~k位置上值大于k的数的个数。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			int t;
			scanf("%d",&t);
			if(i<=k&&t>k) ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
} 

B. Woeful Permutation

题目链接：Problem - B - Codeforces

样例输入： 

2
1
2

样例输出：

1 
2 1 

题意：给定一个n，让我们输出一个1~n的排列p1,p2,……,pn，使得最大。

分析：通过模拟简单的样例可以发现一种简单的构造方式，当n为奇数时，我们将p1赋值为1，然后剩余偶数个数两两一组，交换匹配，当n是偶数时，直接两两一组交换匹配即可，很显然有任意两个相邻的数都是互质的，细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		if(n==1) puts("1");
		else if(n&1)
		{
			printf("1 ");
			for(int i=2;i<=n;i++)
				printf("%d ",i^1);
			puts("");
		}
		else
		{
			for(int i=1;i<=n;i++)
				if(i&1)
					printf("%d ",i+1);
				else
					printf("%d ",i-1);
			puts("");
		}
	}
	return 0;
}

C. Sort Zero

题目链接：Problem - C - Codeforces

样例输入： 

5
3
3 3 2
4
1 3 1 3
5
4 1 5 3 2
4
2 4 1 2
1
1

样例输出：

1
2
4
3
0

题意：给定一个长度为n的数组，我们可以对这个数组进行操作，每次操作可以选择一个x,使得对于所有的i满足ai=x的数都变为0，问使得初始数组变为单调不递减的数组所需要的最少操作次数。

分析：容易发现，当我们把第i个数变为0时，那么前i-1个数都要变为0，所以问题就转化为了求解最靠前的一个位置id使得将前id个位置变为0后数组变为一个非单调递减序列，为什么是最靠前的呢，因为我们发现操作具有单调性，也就是将区间[1,r]全变为0所需要的操作次数一定不会小于将区间[1,l](l肯定要使得满足题意的id尽量小，所以我们从后往前遍历数组，当发现a[i]a[103]，按照我们上述操作会将区间[1,102]中不同数的个数作为答案，但是有可能在区间[1,102]中含有i满足a[i]=a[105]，这样理论上我们也会把105及之前的数全部变为0，所以我们需要记录一下a[i]第一次和最后一次出现的次数，如果是两者中间的数全部等于a[i]的那没有问题，否则一定会有问题，我们发现这样的数之后直接从当前位置向前统计出现的不同的数的个数即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int a[N],last[N],pre[N];
int f[N];//f[i]代表1~i中出现的数字种类 
bool vis[N]; 
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]),last[a[i]]=i,pre[a[i]]=0;
			vis[i]=false;
		}
		f[0]=0;
		for(int i=1;i<=n;i++) 
		{
			if(!pre[a[i]]) pre[a[i]]=i;
			f[i]=f[i-1];
			if(!vis[a[i]]) f[i]++;
			vis[a[i]]=true;
		}
		int ans=0;
		for(int i=n;i>1;i--)
		{
			if(pre[a[i]]!=last[a[i]])
			{
				for(int j=pre[a[i]]+1;j<last[a[i]];j++)
					if(a[j]!=a[i])
					{
						ans=f[i];
						break;
					}
				i=pre[a[i]];
			}
			if(ans) break;
			if(a[i]<a[i-1]) ans=f[i-1];
			if(ans) break;
		}
		printf("%d\n",ans);
	}
	return 0;
}

D. Empty Graph

题目链接：Problem - D - Codeforces

样例输入：

6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2

样例输出：

4
168
10
1000000000
9
1000000000

题意：给定一个长度为n的数组a。

有一个n个点的完全图，l到r（l

分析：我们先不考虑如何进行操作，先看看如何求取两个点之间的路径的最小值，以l和r(l，先来看一下k在区间[l,r]的情况，那么距离就是min{al,al+1,……,ak}+min{ak,ak+1,……,ar}，那么显然有这个距离大于min{al,al+1,……,ar}，拿这显然是不合适的，现在来分析一下k不在区间[l,r]的情况，那么由于贪心策略，k肯定是不在区间[l,r]中的权值最小的点，不妨设点和权值分别为id和w，那么从l到id和从id到r的权值都是w,那么总的权值就是2*w，那么我们取2*w和min{al,al+1,……,ar}中的一个较小值即可，那么问题来了，有没有可能是经过2个以上的中间点呢？答案是否定的，因为不管怎样，每次路径的权值都不可能小于w，那么如果经过了2个中间点，那么权值至少是3*w，这显然是不对的，所以最短路径一定是直接边或者经过一个间接点得到的，我们先来讨论一下区间[l,r]，不妨假设该区间内权值最小的位置是id，那么l到r的直接边权值等于id到他相邻点的权值，所以我们显然可以只考虑两个相邻的点的情况，如果这两个点的点权较小值等于x，如果除了这两个点之外的点有权值小于(x-1)/2的，那么权值就是通过间接点得到的，所以我们就可以萌生一种思路，二分答案x，找两个权值大于等于x的相邻点（这两个点可以是经过操作后点权大于等于x也可以是本身权值就大于等于x），然后保证其他点的权值均大于(x-1)/2（防止该点作为间接点使得直径小于x），这样就能保证直径不会小于x，所以我们只需要判断操作为这样的数组所需要的最少操作次数与k的关系即可，小于等于k则说明x是可以达到的，否则说明x是不可能达到的。细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int a[N],n,k;
int b[N];
bool check(int x)
{
	int cnt=0;//记录小于等于(x-1)/2的值的个数
	int t=0;//记录大于等于x的值的个数 
	for(int i=1;i<=n;i++)
	{
		b[i]=a[i]; 
		if(a[i]<=(x-1)/2) b[i]=1999999999,cnt++;
		if(b[i]>=x) t++;
	}
	for(int i=1;i<n;i++)
	{
		if(b[i]>=x&&b[i+1]>=x) break;
		if(i==n-1)
		{
			if(t==0) cnt+=2;//没有一个值大于等于x
			else cnt+=1;//至少有一个值大于等于x 
		}
	}
	return cnt<=k;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		int l=1,r=1e9;
		while(l<r)
		{
			int mid=l+r+1>>1;
			if(check(mid)) l=mid;
			else r=mid-1;
		}
		printf("%d\n",l);
	}
	return 0;
}