Codeforces Round #813 (Div. 2)A.B.C

A. Wonderful Permutation

题目链接：

Problem - A - Codeforces

题面：

题意：

你可以任意选择两个位置，然后交换两个位置上的数，问：使前k个数相加最小需要交换几次

思路：

我们可以统计最小的k个数有几个的位置大于等于k即可

代码：

#include
using namespace std;
 
struct node{
	int num;
	int i;
}arr[105];
 
bool cmp(node a, node b){
	return a.num < b.num;
}
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n, k;
		cin >> n >> k;
		for(int i = 0; i < n; i++){
			cin >> arr[i].num;
			arr[i].i = i;
		}
		sort(arr, arr + n, cmp);
		int ans = 0;
		for(int i = 0; i < k; i++){
			if(arr[i].i >= k){
				ans++;
			}
		}
		cout << ans << endl; 
	}
	return 0;
}

B. Woeful Permutation

题目链接：

Problem - B - Codeforces

题面：

题意：

一共有n个数，需要构造一个排列p，使得sum（lcm（i， pi））最大

思路：

lcm（n， n-1）一定是所有搭配里面最大的

在区间内lcm（i， i+1）是最大的，我们只需要从大到小把两个相邻的放在一个求lcm即可

代码：

#include
using namespace std;
 
int arr[100005];
 
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i = n; i >= 1; i -= 2){
			if(i > 1){
				arr[i - 1] = i;
				arr[i] = i - 1;
			}else{
				arr[i] = i;
			}
		}
		for(int i = 1; i <= n; i++){
			if(i != 1){
				cout << " ";
			}
			cout << arr[i];
		}
		cout << endl;
	}
	return 0;
}

C. Sort Zero

题目链接：

Problem - C - Codeforces

题面：

题意：

有一个n个数的数组，我们可以选择一个x找到所有ai == x的，并把ai变成0，问最少需要几步能把数组变成非递减数组

思路：

我们从后往前考虑，如果所有的an都是连续的，那么an就不用变成0，然后不断缩小n即可，如果an不是连续的，无论中间的数比an大还是小，我们都需要把前面所有的位置（包括n）的数变成0

代码：

#include
using namespace std;
 
int arr[100005];
vector<int> ve[100005];
bool vis[100005];
int main(){
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++){
			ve[i].clear();
			vis[i] = 0;
		}
		int num = 0;
		for(int i = 1; i <= n; i++){
			cin >> arr[i];
			if(vis[arr[i]] == 0){
				num++;
			}
			vis[arr[i]] = 1;
			ve[arr[i]].push_back(i);
		}
		int ans = 1e5 + 5;
		int cnt = 0;
		for(int i = n; i >= 1; i--){
			int a = arr[i];
//			cout << a << " " << ans << " : ";
			if(a < ans){
				int m = ve[a].size() - 1;
				bool f = 0;
				for(int j = 1; j <= m; j++){
//					cout << ve[a][m - j] << " ";
					if(ve[a][m - j] != i - j){
						f = 1;
						break;
					}
				}
//				cout << endl;
				if(f){
					break;
				}
				cnt++;
				ans = a;
				i = i - m;
			}else{
				break;
			}
		}
//		cout << endl;
		cout << num - cnt << endl;
		
	}
	return 0;
}