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 int

const int eps=1e-;

const int INF=;

const int maxn=+;

const LL mod=***;

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)==&&n)

    {

        ans=;

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

        {

            scanf("%I64d%I64d",&que[i].a,&que[i].b);

        }

        sort(que,que+n,cmp);

        for(int i=;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 ;

}