但是 rul out 规模 pan 宽度 面积 travel 一起
【问题描述】
假设这是一个二次元。
LYK召集了n个小伙伴一起来拍照。他们分别有自己的身高Hi和宽度Wi。
为了放下这个照片并且每个小伙伴都完整的露出来,必须需要一个宽度为ΣWi,长度为max{Hi}的相框。(因为不能叠罗汉)。
LYK为了节省相框的空间,它有了绝妙的idea,让部分人躺着!一个人躺着相当于是身高变成了Wi,宽度变成了Hi。但是很多人躺着不好看,于是LYK规定最多只有n/2个人躺着。(也就是说当n=3时最多只有1个人躺着,当n=4时最多只有2个人躺着)
LYK现在想问你,当其中部分人躺着后,相框的面积最少是多少。
【输入格式】
第一行一个数n。
接下来n行,每行两个数分别是Wi,Hi。
【输出格式】
你需要输出这个相框的面积最少是多少。
【样例输入】
3
3 1
2 2
4 3
【样例输出】
27
【样例解释】
如果没人躺过来,需要27的面积。
我们只要让第1个人躺过来,就只需要21的面积!
【数据规模与约定】
对于30%的数据n<=10。
对于60%的数据n<=1000,Wi,Hi<=10。
对于100%的数据1<=n,Wi,Hi<=1000。
题解:
①先去掉一个限制,方法是枚举最大高度H,贪心分类讨论:
·贪心策略:在高度不超过限制的情况下,使宽度增加尽可能少。
设h,w分别为当前人的高和宽,那么:
(1)h>H:
w>H:躺着还是会超出高度,不合法直接跳出。
w<=H:躺着
(2)h<=H:
h>=w:站着(这样宽度增加得少)
h<w:躺着,但是由于躺的人数有限制,所以有一部分还是要站着。
因此特殊处理这种需要决策的情况(在h<=H&&h<w的这种情况下):
问题:这些人站着躺着的高度都不会超出H,因此考虑怎样选择使得总宽度最少。
解决方案:先让每个人都站着,此时总宽度设为W,然后再让n/2个人躺下:
每个人躺下,那么这个人对W将加上值(h-w) (意思是将宽换成高的长),
那么我们希望(h-w)尽量小,因此从小到大排序然后取前n/2个躺着就可以了。
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <map>
- using namespace std;
- set<int> ::iterator sit;
- int ans,sum,p[1005],i,a[1005],b[1005],cnt,CNT,j,ANS,n;
- int cmp(int i,int j) {return i>j;}
- bool FLAG;
- int main()
- {
- ANS=1000000000;
- scanf("%d",&n);
- for (i=1; i<=n; i++)
- scanf("%d%d",&a[i],&b[i]);
- for (i=1; i<=1000; i++)
- {
- sum=0; FLAG=true; cnt=0; CNT=0;
- for (j=1; j<=n; j++)
- if (b[j]<=i && (a[j]<=b[j] || a[j]>i)) sum+=a[j]; else
- if (a[j]>i && b[j]>i) {FLAG=false; break;} else
- if (b[j]>i) {cnt++; sum+=b[j];} else
- {
- p[++CNT]=a[j]-b[j];
- sum+=a[j];
- }
- if (!FLAG) continue;
- if (cnt>n/2) continue;
- sort(p+1,p+CNT+1,cmp);
- for (j=1; j<=min(n/2-cnt,CNT); j++) sum-=p[j];
- ANS=min(ANS,sum*i);
- }
- cout<<ANS;
- return 0;
- }//Ztraveler
每当我在路上停下脚步,望着天空我都会看到你。
每当我从荒芜的梦中惊醒,留着眼泪我都能感觉到你。————汪峰《母亲》
【ZBH选讲·拍照】
来源: http://www.bubuko.com/infodetail-2349371.html