清北学堂模拟赛d1t5 拍照(photo)

题目描述
假设这是一个二次元。
LYK召集了n个小伙伴一起来拍照。他们分别有自己的身高Hi和宽度Wi。
为了放下这个照片并且每个小伙伴都完整的露出来，必须需要一个宽度为ΣWi，长度为max{Hi}的相框。（因为不能叠罗汉）。
LYK为了节省相框的空间，它有了绝妙的idea，让部分人躺着！一个人躺着相当于是身高变成了Wi，宽度变成了Hi。但是很多人躺着不好看，于是LYK规定最多只有n/2个人躺着。（也就是说当n=3时最多只有1个人躺着，当n=4时最多只有2个人躺着）
LYK现在想问你，当其中部分人躺着后，相框的面积最少是多少。

输入格式(photo.in)
第一行一个数n。
接下来n行，每行两个数分别是Wi,Hi。

输出格式(photo.out)
你需要输出这个相框的面积最少是多少。

输入样例
3
3 1
2 2
4 3

输出样例
21

样例解释
如果没人躺过来，需要27的面积。
我们只要让第1个人躺过来，就只需要21的面积！

对于30%的数据n<=10。
对于60%的数据n<=1000，Wi,Hi<=10。
对于100%的数据1<=n,Wi,Hi<=1000。

分析：陷入了dp的死胡同.......以为就是一个三维dp，结果复杂度爆表了，正解竟然是贪心......

其实正解是贪心也很正常，数据这么大能做到这么快求解的也就只有贪心和数学方法了.那么要怎么贪心呢？因为每次旋转一个人都要涉及到高度和长度的变化，我们人为限定一个高度.枚举这个高度i，

如果h > i && w <= i必须躺
如果h <= i && w > i不能躺
如果h <= i && w <= i
如果h >= w,不躺
如果h < w,躺，并且将w - h排序，将剩下没有用完的次数给用完就可以了.

思路比较巧，也有很多实用的技巧，如果对于高度和宽度的变化不好把控，人为规定一个高度就行了.数据比较大有一定可能是贪心题.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int inf = 0x7fffffff;

int n, w[], h[], ans = inf,cnt,tot,e[];

bool cmp(int a, int b)

{

    return a > b;

}

int main()

{

    scanf("%d", &n);

    for (int i = ; i <= n; i++)

        scanf("%d%d", &w[i], &h[i]);

    for (int maxn = ; maxn <= ; maxn++)

    {

        bool flag = false;

        int sum = ;

        cnt = tot = ;

        for (int i = ; i <= n; i++)

        {

            if (h[i] > maxn && w[i] > maxn)

            {

                flag = ;

                break;

            }

            if (h[i] > maxn && w[i] <= maxn)

            {

                cnt++;

                sum += h[i];

            }

            else

                if (h[i] <= maxn && (w[i] > maxn || h[i] >= w[i]))

                    sum += w[i];

                else

                    if (h[i] <= maxn && w[i] <= maxn && h[i] < w[i])

                    {

                        e[++tot] = w[i] - h[i];

                        sum += w[i];

                    }

        }

        if (flag)

            continue;

        if (cnt > n / )

            continue;

        sort(e + , e +  + tot, cmp);

        for (int i = ; i <= min(n / -cnt,tot); i++)

            sum -= e[i];

        ans = min(ans, sum * maxn);

    }

    printf("%d\n", ans);

    return ;

}

巴特西

清北学堂模拟赛d1t5 拍照(photo)

最新文章

热门文章