贪心EX

chc_1234567890 · 2018-10-24 12:40:06 · 题解

贪心是一种奇妙的算法，能将O(n^2)、O(n^3)的dp，O(2^n)、O(n!)的爆搜直接化成O(n)。

国王游戏 link

本题需要高精，在此不细讲。

分析

我们考虑两个大臣p_1,p_2，它们站在国王p_0的身后，则这两个大臣有两种排列方案：

1.

2.

对于第一种情况，答案ans_1=\max(\frac{a_0}{b_1},\frac{a_0a_1}{b_2})

对于第二种情况，答案ans_2=\max(\frac{a_0}{b_2},\frac{a_0a_2}{b_1})

显然，\frac{a_0a_1}{b_2}>\frac{a_0}{b_2},\frac{a_0a_2}{b_1}>\frac{a_0}{b_1}

若ans_1<ans_2,\because \frac{a_0a_2}{b_1}>\frac{a_0}{b_1},\therefore \frac{a_0a_2}{b_1}必须>\frac{a_0a_1}{b_2}

即 \frac{a_2}{b_1}>\frac{a_1}{b_2} 即 a_1b_1<a_2b_2

因此，若a_1b_1<a_2b_2，就有p_1排在p_2前更优。

按照上述条件sort一遍，再计算答案即可。

Code

#include<cstdio>
#define maxn 4010
using namespace std;
class hp{
　　public:
    int a[maxn];
    hp(){memset(a,0,sizeof(a));}
    void clear(){memset(a,0,sizeof(a));}
    hp(int x){
        clear();
        while(x){
            a[++a[0]]=x%10;
            x/=10;
        }
        while(a[a[0]]==0&&a[0])a[0]--;
    }
    hp& operator=(int x){
        clear();
        while(x){
            a[++a[0]]=x%10;
            x/=10;
        }
        while(a[a[0]]==0&&a[0])a[0]--;
        return *this;
    }

    short cmp(const hp& x){
        if(a[0]>x.a[0])return 1;
        if(a[0]<x.a[0])return -1;
        for(register int i=a[0];i>=1;i--){
            if(a[i]>x.a[i])return 1;
            if(a[i]<x.a[i])return -1;
        }
        return 0;
    }
    bool operator>(const hp& x){
        return cmp(x)==1;
    }
    bool operator==(const hp& x){
        return cmp(x)==0;
    }
    bool operator<(const hp& x){
        return cmp(x)==-1;
    }
    bool operator>=(const hp& x){
        return !(*this<x);
    }
    bool operator<=(const hp& x){
        return !(*this>x);
    }

    hp operator-(const hp& x){
        hp a=*this,c;
        c.a[0]=a.a[0]>x.a[0]?a.a[0]:x.a[0];
        for(register int i=1;i<=c.a[0];i++) {
            c.a[i]+=a.a[i]-x.a[i];
            if(c.a[i]<0){c.a[i]+=10;a.a[i+1]--;}
        }
        while(c.a[c.a[0]]==0&&c.a[0])c.a[0]--;
        return c;
    }
    hp operator*(const hp& x){
        hp c;
        for(register int i=1;i<=a[0];i++){
            for(register int j=1;j<=x.a[0];j++){ 
                c.a[i+j-1]+=a[i]*x.a[j];
            }
        }
        c.a[0]=a[0]+x.a[0];
        for(register int i=1;i<=c.a[0];i++){
            if(c.a[i]>=10){
                c.a[i+1]+=c.a[i]/10;
                c.a[i]%=10;
            }
        }
        while (c.a[c.a[0]]==0&&c.a[0]>0)c.a[0]--;
        return c;
    }
    hp operator/(const int& x){
        hp c;
        int t=0,s=0;
        bool flag=1;
        for(register int i=a[0];i>=1;i--){
            t=s*10+a[i];
            if(t/x>0||t==0){
                c.a[++c.a[0]]=t/x;
                s=t%x;
                flag=0;
            }
            else{
                s=t;
                if(!flag)c.a[++c.a[0]]=0;
            }
        }
        reverse(c.a+1,c.a+c.a[0]+1);
        return c;
    }
};

struct node{
    int a,b;
};
node a[1001];
bool cmp(node x,node y){
    return x.a*x.b<y.a*y.b;
}
void checkmax(hp& x,hp y){
　　if(x<y)x=y;
}
int main(){
    int n;scanf("%d",n);
    for(register int i=0;i<=n;i++){
        scanf("%d%d",a[i].a,a[i].b);
    }
    sort(a+1,a+n+1,cmp);
    hp ans=0,ji=a[0].a;
    for(register int i=1;i<=n;i++){
        checkmax(ans,ji/a[i].b);
        ji=ji*a[i].a;
　　}
　　if(ans.a[0]==0)putchar('0');
　　else for(register int i=ans.a[0];i>=1;i--)
　　　　putchar(ans.a[i]+'0');
　　return 0;
}

补充题目：打CF

题意

一场CF比赛，时间为T分钟，有N道题，可以在比赛时间内的任意时间提交代码

第i道题的分数为maxPoints[i],题目的分数随着比赛的进行，每分钟减少pointsPerMinute[i]

这是一场比较dark的CF，分数可能减成负数

已知第i道题需要花费requiredTime[i]的时间解决

请问最多可以得到多少分

数据范围

分析

贪心思维题。

声明：在下面的分析中，我们约定

#define a maxPoints
#define b pointsPerMinute
#define c requiredTime

我们考虑两道题p_1,p_2，则先做p_1再做p_2能获得的分数为a_1-b_1c_1+a_2-b_2(c_1+c_2)先做p_2再做p_1能获得的分数为a_2-b_2c_2+a_1-b_1(c_2+c_1) 答案为ans_1,ans_2

若ans_1<ans_2，则

而ans_1<ans_2代表p_2放在p_1前更优，因此，使得p_1放在p_2前更优的条件是b_2c_1<b_1c_2

按照此条件对每一道题排序。

设做掉题目p_i的时刻为time，则p_i的实际得分为a_i-b_i* time

但由于比赛有时间限制，且题目最终得分可能为负数，因此，需要使用01背包来选择。转移方程：

Code

#include<cstdio>
#define maxn 55
#define maxt 100005
using namespace std;
typedef long long D;
inline D max(D x,D y){return x>y?x:y;}
D a[maxn],b[maxn],c[maxn],tot,dp[maxt],ans;
int cnt,n,t[maxn];
bool cmp(int i,int j){
　　return b[j]*c[i]<b[i]*c[j];
}
int main(){
　　scanf("%d%lld",n,tot);
　　for(int i=1;i<=n;i++)scanf("%lld",a[i]);
　　for(int i=1;i<=n;i++)scanf("%lld",b[i]);
　　for(int i=1;i<=n;i++)scanf("%lld",c[i]),t[i]=i;
　　sort(t+1,t+n+1,cmp);
　　for(int i=1;i<=n;i++){
        for(int j=tot;j>=c[t[i]];j--){
            dp[j]=max(dp[j],dp[j-c[t[i]]]+a[t[i]]-b[t[i]]*j);
            ans=max(ans,dp[j]);
        }
    }
　　printf("%lld\n",ans);
　　return 0;
}

请勿抄袭，否则后果自负