网站页面布局的目的,建设网站如何挂到网上,搜索引擎营销的五大特点,专业app开发制作团队【问题描述】 假设这是一个二次元。LYK召集了n个小伙伴一起来拍照。他们分别有自己的身高Hi和宽度Wi。为了放下这个照片并且每个小伙伴都完整的露出来#xff0c;必须需要一个宽度为ΣWi#xff0c;长度为max{Hi}的相框。#xff08;因为不能叠罗汉#xff09;。LYK为了节省…【问题描述】 假设这是一个二次元。LYK召集了n个小伙伴一起来拍照。他们分别有自己的身高Hi和宽度Wi。为了放下这个照片并且每个小伙伴都完整的露出来必须需要一个宽度为ΣWi长度为max{Hi}的相框。因为不能叠罗汉。LYK为了节省相框的空间它有了绝妙的idea让部分人躺着一个人躺着相当于是身高变成了Wi宽度变成了Hi。但是很多人躺着不好看于是LYK规定最多只有n/2个人躺着。也就是说当n3时最多只有1个人躺着当n4时最多只有2个人躺着LYK现在想问你当其中部分人躺着后相框的面积最少是多少。【输入格式】 第一行一个数n。接下来n行每行两个数分别是Wi,Hi。 【输出格式】 你需要输出这个相框的面积最少是多少。【样例输入】 33 12 24 3【样例输出】 27【样例解释】如果没人躺过来需要27的面积。我们只要让第1个人躺过来就只需要21的面积【数据规模与约定】对于30%的数据n10。对于60%的数据n1000Wi,Hi10。对于100%的数据1n,Wi,Hi1000。 题解 ①先去掉一个限制方法是枚举最大高度H,贪心分类讨论: ·贪心策略在高度不超过限制的情况下使宽度增加尽可能少。 设h,w分别为当前人的高和宽那么 (1)hH: wH:躺着还是会超出高度不合法直接跳出。 wH:躺着 (2)hH: hw:站着(这样宽度增加得少) hw:躺着但是由于躺的人数有限制所以有一部分还是要站着。 因此特殊处理这种需要决策的情况(在hHhw的这种情况下) 问题这些人站着躺着的高度都不会超出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;
setint ::iterator sit;
int ans,sum,p[1005],i,a[1005],b[1005],cnt,CNT,j,ANS,n;
int cmp(int i,int j) {return ij;}
bool FLAG;
int main()
{ANS1000000000;scanf(%d,n);for (i1; in; i)scanf(%d%d,a[i],b[i]);for (i1; i1000; i){sum0; FLAGtrue; cnt0; CNT0;for (j1; jn; j)if (b[j]i (a[j]b[j] || a[j]i)) suma[j]; elseif (a[j]i b[j]i) {FLAGfalse; break;} elseif (b[j]i) {cnt; sumb[j];} else{p[CNT]a[j]-b[j];suma[j];}if (!FLAG) continue;if (cntn/2) continue;sort(p1,pCNT1,cmp);for (j1; jmin(n/2-cnt,CNT); j) sum-p[j];ANSmin(ANS,sum*i);}coutANS;return 0;
}//Ztraveler 每当我在路上停下脚步望着天空我都会看到你。 每当我从荒芜的梦中惊醒留着眼泪我都能感觉到你。————汪峰《母亲》转载于:https://www.cnblogs.com/Damitu/p/7661295.html
