首页 > 代码库 > hdu4442 Physical Examination(贪心)
hdu4442 Physical Examination(贪心)
这种样式的最优解问题一看就是贪心。如果一下不好看，那么可以按照由特殊到一般的思维方式，先看n==2时怎么选顺序（这种由特殊到一般的思维方式是思考很多问题的入口）：
有两个队时，若先选第一个，则ans=a1+a2+b2*a1;若先选第二个，则ans=a2+a1+b1*a2;所以选择顺序就比b2*a1和b1*a2就好了。
那么当有n>2个队时，能不能也这么搞？当然可以，每次剩下那几个队没选，我就两两比，两两之间比较时，之前用的时间都要加上是和顺序无关的，顺序影响的只是b2*a1和b1*a2而已（如果想不通也可以写出数学表达式消项观察）。那么我两两之间全比完以后就选那个当前最小的就是当前最优解。为了方便，反正每次选最小，所以事先把n个队排好序然后直接算就行了。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=100000+10;const LL mod=365*24*60*60;int n;struct node{ LL a,b;}que[maxn];bool cmp(node x,node y){ return x.a*y.b<x.b*y.a;}LL ans;int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d",&n)==1&&n) { ans=0; for(int i=0;i<n;i++) { scanf("%I64d%I64d",&que[i].a,&que[i].b); } sort(que,que+n,cmp); for(int i=0;i<n;i++) { //cout<<que[i].a<<‘ ‘<<que[i].b<<endl; ans+=(que[i].a+(ans*que[i].b)%mod)%mod; } printf("%I64d\n",ans%mod); } //fclose(stdin); //fclose(stdout); return 0;}
hdu4442 Physical Examination(贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。