专栏文章

题解：CF525C Ilya and Sticks

OOIerJiang_1017
CF525C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqn2xpf
此快照首次捕获于
2025/12/04 07:29
3 个月前
此快照最后确认于
2025/12/04 07:29
3 个月前
查看原文

CF525C 题目传送门

题目大意

给定 nn 根木棍，第 ii 根木棍的长度为 fif_i ，木棍长度可以根据需要，削减 11 个单位，现在要在 nn 根木棍中选出一些木棍，拼成若干个长方形，求这些长方形面积总和的最大值。

解决思路

题目中已经说了一根木棍只能削掉 11 个单位，说明组成长方形时两根木棍如果想配对（让两根木棍长度相等），它们的差就只能是 00 或者 11 。为了方便对木棒进行配对，我们需要对木棍的长度进行排序。同时要让面积尽量大，所以要从大到小排序。

分析样例

接下来就需要进行模拟。此处给一个样例方便理解。假设排完序后所有木棍的长度如下：{13,12,10,9,7,6,5,3,2}\{13,12,10,9,7,6,5,3,2\}。很明显，为了配对，我们需要把 1313 削成 1212，两个 1212 可以配对。把 1010 削成 1212，两个 99，可以配对。把 77 削成 66，两个 66，可以配对。55 只能削 11 单位，削成 44，无法与其他进行配对。33 可以削成 22，两个 22，可以配对。配对完一共有 44 个配对，长度分别为 {12,9,6,2}\{12,9,6,2\}。第一个长方形长为 1212，宽为 99；第二个长方形长为 66，宽为 22。

发现规律

分析完样例就容易发现规律：大到小排序后，从 f2f_2 到 fnf_n 进行枚举，如果相邻两根的长度差小于 11，就可以把它作为长，注意这两根已经选的不能再选，接下来再遇到相邻两根长度差小于 11 的就作为宽，算出这个长方形的面积并加入结果中，将长与宽都清 00，方便接下来统计。

代码展示

CPP
#include <iostream>
#include <algorithm>
#define ll long long
//不开long long见祖宗
using namespace std;

const int N = 1e5 + 10;
ll n, f[N], a, b;
bool cmp(ll x, ll y)
{
	return x > y;
}

int main()
{
	scanf("%lld", &n);//建议scanf,更快
	for(int i = 1; i <= n; i++)
		scanf("%lld", &f[i]);
	sort(f + 1, f + n + 1, cmp);
	for(int i = 2; i <= n; i++)
		if(f[i - 1] - f[i] <= 1)
			if(a != 0)
			{
				b += a * f[i];
				a = 0;
				i++;
			}
			else
			{
				a = f[i];
				i++;
			}
	printf("%lld\n", b);//建议printf,更快
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...