题解 [NOI2004]小H的小屋
前记
又鸽了好久,这回可要努力更新了
2019.6.2,痛下杀心,把电脑上所有的游戏都删掉了,提前160天奋力备考NOIP。目标:A类省队!
题解
这道题唯一的难点就在于贪心
从简单开始,假如一个矩形需要分成两部分,要求面积最小(参照题意)。那么均分肯定时最优解
如图,紫色是大的矩形,橙色是均分的两个小矩形,蓝色是非均分的两个小矩形。显而易见的是,橙色面积要比蓝色小。由于是贪心嘛其实是懒得严格证明,我们发现分成两个的情况下,均分最优
那么把情况扩展以下,由于贪心思想这回是因为我不会严格证明,均分思想可以推广到分成更多的小矩形的情况中
好了有了均分的思想,还有一个问题:假如(n mod m ne 0) 怎么办?
也好办,尽可能凑成对齐的就好了嘛
| 北墙 | 南墙 |
- | :-: | :-: |
一部分 | (ln = m-nmod m) | (lr = lfloor frac{n}{m} rfloor)
另一部分 | (rn = nmod m) | (rs = lfloor frac{n}{m} rfloor + 1)
酱紫就可以保证满足均分思想
假设(area(x,y,k))表示在横坐标长度为y的矩形中分x份,斜率为k
double area(int x,int y,double k){ // x kuai in y len
return (double)(x-y%x)*(y/x)*k*(y/x)+(y%x)*(y/x+1)*k*(y/x+1);
}
当(nmod m=0)时
(ans=area(n,100,k1)+area(m,100,k2))
当(nmod mne 0)时
(ans=min_{i=lntimes lr} ^ {100-rn*rs} area(ln,i,k1)+area(lntimes ls,i,k2)+area(rn,100-i,k1)+area(rntimes rs,100-i,k2))
然后据说ans关于i是个单峰函数,不过反正i最大不过循环100次,我也不会证明这个函数的单调性,就算了吧。
code:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m,n,ln,ls,rn,rs;
double k1,k2,ans;
double area(int,int,double);
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
#endif
scanf("%lf%lf%d%d",&k1,&k2,&m,&n);
if(n%m==0){
ans+=area(m,100,k1);
ans+=area(n,100,k2);
printf("%.1lfn",ans);
return 0;
}
ln=m-n%m; ls=n/m;
rn=n%m; rs=(n/m+1);
ans=2147483647.0;
for(int i=ln*ls;i<=100-rn*rs;++i){
double tmp=0.0;
tmp+=area(ln,i,k1);
tmp+=area(ln*ls,i,k2);
tmp+=area(rn,100-i,k1);
tmp+=area(rn*rs,100-i,k2);
ans=min(ans,tmp);
}
printf("%.1lfn",ans);
return 0;
}
double area(int x,int y,double k){ // x kuai in y len
return (double)(x-y%x)*(y/x)*k*(y/x)+(y%x)*(y/x+1)*k*(y/x+1);
}
后记
距 NOIp2019 还剩 159 天
你已经在洛谷连续打卡了 266 天,奖励积分 4
冲鸭!
原文链接: https://www.cnblogs.com/ticmis/p/13210813.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360376
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!