题解：CF525C Ilya and Sticks

· · 题解

CF525C 题目传送门

题目大意

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

解决思路

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

分析样例

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

发现规律

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

代码展示

#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;
}