813(Div.2)A~C

Codeforces Round #813 (Div. 2)

A. Wonderful Permutation

题目大意：

给定一个长度为n的序列和一个正整数k。

在一次操作中，可以对$i$和$j(1 \le i\lt j \le n)$交换$p_i$和$p_j$。

为了使$p_1 + p_2 + ...+p_k$的总和尽可能的小，最少需要多少次操作？

思路：

对于一个序列的前$k$项，一定是$1+2+...+k$的总和是最小的。

所以我们只要统计给定的序列$p$的前$k$项中有几个是大于$k$的即可，对于这些不在1~$k$范围内的元素要进行交换。

AC Code

void solve()
{
	int n,k;
	cin >> n >> k;
	vector<int> a(n + 1);
	map<int,int> mp;
	for (int i = 1;i <= n;i ++)
	{
		cin >> a[i];
		if (i <= k)	mp[a[i]] = 1; 
	}
	
	int ans = 0;
	for (int i = 1;i <= k;i ++)
		if (mp[i] == 0)	ans ++;
	
	cout << ans << endl;
}

B. Woeful Permutation

题目大意：

给定一个正整数n，要求构造一个permutation使得每一个$i$和$p_i$的最小公倍数之和最大。

思路：

由于相邻的两个数一定互质，而互质数的最小公倍数最大，所以当只要输出两个相邻的数即可。

当n为奇数时，先输出一个1，然后从i从2开始输出i+1和i

当n为偶数时，i从1开始输出i+1和i

AC Code

void solve()
{
	int n;
	cin >> n;
	
	if (n & 1)
	{
		cout << 1 << ' ';
		for (int i = 2;i <= n;i += 2)		
			cout << i + 1 <<  ' ' << i << ' ';
	}
	else
		for (int i = 1;i <= n;i += 2)	
			cout << i + 1 << ' ' << i << ' ';
	
	puts("");
}

C. Sort Zero

题目大意：

给定一个长度为n的正整数数组。

在一次操作内：

1.选择一个整数数$x$

2.对于数组中所有值等于$x$的元素，全部将其改变成0

求最少多少次操作可以使得这个数组成为非递减排序

思路：

要想成为非递减排序，任意一个0的前面都应该是0，也就是说如果数组中间出现一个0，那么这个0的前面都应该是0才符合要求。

所以我们要找到的就是最后一个0出现的位置，也就是最后一个a[i] > a[i + 1]的位置$idx$。

然后统计$idx$前的有多少个不同的数字，在找到$idx$后最后一个被统计过的元素，枚举$idx$到最后一个被统计过的元素之间有几个未被统计过的元素。

AC Code

void solve()
{
	int ans = 0;
	int n;
	cin >> n;
	vector<int> cnt;
	vector<int> a(n + 1);
	map<int,int> mp;
	for (int i = 1;i <= n;i ++)
		cin >> a[i];
		
	int idx = n;
	for (int i = n;i > 1;i --)
		if (a[i] < a[i - 1])	break;
		else idx = i - 1;
	
	for (int i = 1;i < idx;i ++)
		if (mp[a[i]] == 0)
		{
			ans ++;
			mp[a[i]] = 1;
		}
	
	for (int i = n;i >= idx;i --)
	{
		if (mp[a[i]])
		{
			for (int j = i;j >= idx;j --)
				if (mp[a[j]] == 0)
				{
					ans ++;
					mp[a[j]] = 1;
				}
			break;
		}
	}
	cout << ans << endl;
}