Educational Codeforces Round 69 (Rated for Div. 2)

最新推荐文章于 2020-05-26 21:52:25 发布

淼润淽涵

最新推荐文章于 2020-05-26 21:52:25 发布

阅读量142

点赞数

分类专栏： Codeforces

本文链接：https://blog.csdn.net/wcxyky/article/details/104199948

版权

Codeforces 专栏收录该内容

5 篇文章

订阅专栏

本文精选了四道算法竞赛题目并提供了详细的解题思路及代码实现，包括排序、动态规划和序列分析等核心算法概念。通过这些题目的解析，读者可以深入理解算法设计的基本原理，并提升解决实际问题的能力。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

A：

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int t,n,a[100005];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		scanf("%d",a[i]);
		sort(a,a+n);
		printf("%d\n",min(n-2,a[n-2]-1));
	}
}

B（思维题）:

题意：

给出n个柱子，每个柱子一个圆盘，其半径各不相同，每次只能将柱子上只有一个圆盘的移到相邻位置，问能否全部移到一个柱子上。

思路：

要想全部移到一根柱子上，这个序列必须为前半部分递增，后半部分递减，或全部递增或递减。

代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n, a[200005], k;
	scanf("%d", &n);
	for (int i = 0; i <n; i++) {
		scanf("%d", &a[i]);
		if (a[i] == n) k = i; // 最大数位置 
	}
	int flag = 0;
	for (int i = 0; i < k; i++) { // 判断最大数前面的数据是否递增 
		if (a[i] > a[i+1]) flag = 1;
	}
	for (int i = k; i < n - 1; i++) { // 判断最大数后面的数据是否递减 
		if (a[i+1] > a[i]) flag = 1;
	}
	if (!flag) printf("YES\n");
	else printf("NO\n");
	return 0;
}

C：

题意：

这个题的意思就是给你一个数n和一个数字k，然后输入从小到大排列好的n个数字，让你把这n个数字分成k组，分成的每一组的成本就是这个组里面数字的最大减最小，求分成k组成本最小。

思路：

代码：

#include <cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

ll p[300005];
int main() {
	int n, k; cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	if (k >= n)
		cout << "0" << endl;
	else {
		for (int i = n - 1; i > 0; i--) {
			p[i] = p[i] - p[i - 1];
		}
		p[0] = 0;
		sort(p, p + n);
		ll ans = 0;
		for (int i = 0; i <= n - k; i++)
			ans += p[i];
		cout << ans << endl;

	}
}

D：