贪心学习小结-12138

贪心

贪心算法所做的选择可以依赖于之前所做的选择，但绝不依赖未来的选择。

贪心必须对每个子问题的解都做当前最好的选择，而不关心未来的选择；动态规划则会根据之前的结果对当前进行选择。

贪心是自顶向下的方式进行。

贪心策略的确定：
1、根据经验
2、根据结果回推前几步，用数学归纳法找出贪心策略 添加链接描述

题目小结

混合牛奶
就是一个贪心背包问题，先买奶便宜量大的，排序即可

#include 
#define eps 1e-15
using namespace std;
void solve(){

}
struct milk{
    int p,sn;
};
bool cmp(const milk a, const milk b){
    if(a.p<b.p)return true;
    else if(a.p==b.p)return a.sn-b.sn;
    else return false;
}
milk mi[2000005];
//全局变量再访问时越界也不会报错，会访问超出的内存空间
int main()
{
    long long sum=0;
    int m,n,i,num=0;
	cin>>m>>n;
	for(i=1;i<=n;i++)cin>>mi[i].p>>mi[i].sn;
    //if(m==0 ){cout<<0;return 0;}
	sort(mi+1,mi+1+n,cmp);
	i=1;
	/*for(i=1;i<=10;i++)cout<
	//这里最好不要用<=不然会出现while一直循环的情况（如果num+0==m）
	while(num+mi[i].sn<m){
        num+=mi[i].sn;
        sum+=mi[i].p*mi[i].sn;
        i++;
	}
	/*cout<
    if(num<m){sum += mi[i].p*(m-num);}
    cout<<sum;
    return 0;
}

排队接水
多处最优服务次序问题的简化，先服务耗时短的人。

#include 
#define eps 1e-15
using namespace std;
void solve(){

}
struct person{
    int t,f;
};
bool cmp(const person a, const person b){
    return a.t<b.t;
}
int main()
{
    double ans=0;
    int n;
    person p[1005];
    cin>>n;
	for(int i=1; i<=n; i++){cin>>p[i].t;p[i].f=i;}
	sort(p+1,p+1+n,cmp);
	for(int i=1; i<=n; i++){
        ans += (n-i)*p[i].t;
	}
	for(int i=1; i<=n; i++)
        cout<<p[i].f<<" ";
    printf("\n%.2lf", ans/n);
    return 0;
}

排座椅
因为每一次划线对一名同学最多隔离一个同学，所以直接找出说话最多的每行每列画线即可。

但以后需要仔细读题，输出要求是行号列号从小到大。

#include 
#define eps 1e-15
using namespace std;
struct s{
    int f,n;
}r[2005],c[2005];
bool cmp(const s a, const s b){
    return a.n>b.n;
}
int main()
{
    int m,n,k,l,d,r1,r2,c1,c2;
    int a[2005];
    cin>>m>>n>>k>>l>>d;
    for(int i=1; i<=m; i++)
        r[i].f=i;
    for(int i=1; i<=n; i++)
        c[i].f=i;
    for(int i=1; i<=d; i++){
        cin>>r1>>c1>>r2>>c2;
        if(r1==r2){c[c1>c2?c2:c1].n++;}
        else if(c1==c2){r[r1>r2?r2:r1].n++;}
    }
	sort(r+1,r+1+m,cmp);
	sort(c+1,c+1+n,cmp);
//输出
	for(int i=1; i<=k; i++)
        a[i]=r[i].f;
    sort(a+1,a+1+k);
    for(int i=1; i<=k; i++)
        cout<<a[i]<<" ";
    cout<<endl;
	for(int i=1; i<=l; i++)
        a[i]=c[i].f;
    sort(a+1,a+1+l);
    for(int i=1; i<=l; i++)
        cout<<a[i]<<" ";
    return 0;
}

守望者的逃离
这个题做的我要死了，用贪心好多情况需要考虑，太费脑子了。

分析：
判断使用闪烁优还是跑步优，如果不能逃出距离更远好，如果能逃出时间更短好。

先用魔力完成闪烁，保证时间够且距离

然后魔力可分为3种情况：
1、0-1，需要4秒才能完成闪烁60m，跑步能68m
2、2-5，需要3秒才能完成闪烁60m，跑步能跑51m
3、6-9，需要2秒才能完成闪烁60m，跑步能跑34m
第一种情况闪烁完后成为第二种情况。

完成两次跳跃7秒，120m，跑步119m。

每次算出跑步需要的时间，进行一次闪烁需要的时间

if 最后几秒跑步能跑到终点 && 时间少于闪烁，那就跑步。

else if 第2、3情况 && 时间足够，闪烁
else if 第1种情况 && 时间足够 && 少于跑步到终点的时间，闪烁。

int main()
{
    int m,s,t,maxx=0,t1;
    cin>>m>>s>>t;
    t1=t;
    while(t1>0 && m/10 && maxx<s){
        maxx+=60;
        t1--;
        m-=10;
    }
    int t2,t3;
    while(t1 && maxx<s){
        t2=ceil((double)(10-m)/4)+1;
        t3=ceil((double)(s-maxx)/17);
        if(t3 < t2){maxx+=t3*17; t1=t1-t3;}
        else if(t2<=3 && t2<=t1){maxx+=60; m=m+(t2-1)*4-10; t1-=t2;}
        else if(t2==4 && t1>=7 && t3>=7){maxx+=120; m=m+5*4-20; t1-=7;}
        else {maxx+=17; t1--;}
        }
        if(maxx>=s)cout<<"Yes"<<endl<<t-t1;
        else cout<<"No"<<endl<<maxx;
    return 0;
}

铺设道路
一开始想的是模拟，感觉时间复杂度是低于n^2的，TLE了。

贪心的思路是画一下道路图，模拟一下前几步，总结下规律。

例如4 3 2 5 3 5，第一天肯定能全填2个单位，变成2 1 0 3 1 3，2被填完肯定需要两天，且比2低的也能被填完，第一个3被填完需要3天，且比3低的也能被填完。

第二个3被填完只需要2天。

到此贪心策略就很简单了，只需要每一个上升段最大数减去最小数。

#include 
#define eps 1e-15
using namespace std;
int main()
{
    int n,a[100005];
    long long int ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++){
        if(a[i]>a[i-1])ans+=a[i]-a[i-1];
    }
    cout<<ans;
    /*int n,a[100005],i,j,minn;cin>>n;
    long long int ans=0,f;
	for(i=1; i<=n; i++)cin>>a[i];
	a[0]=0;a[n+1]=0;
	while(1){
        i=0;j=1;
        f=ans;minn=0x7fffffff;
        while(i!=n+1){
            if(a[j]!=0){if(a[j]0){for(int k=i+1; k<=j-1; k++)a[k]-=minn;ans+=minn;i=j;j++;}
            else {i=j;j++;}
        }
        for(int i=1; i<=n; i++)cout<
    return 0;
}

三国游戏
由题意可知人类不可能以最大的组合取胜于机器人，且机器人不可能获胜。

我们可以将每个组合值按升序排列，从大到小选择。

那后续选择可以分成以下几种情况：
1、人类拥有当前组合的其中一个武将，显然人类可以以当前组合获胜。

2、机器人拥有当前组合的一个武将，不可能情况。

3、当前组合的武将是自由的，人类选择其中一个武将，此武将在后续选择中，最快被遇到。

4、机器人拥有当前组合的武将，不可能情况。

根据人类获胜情况可以写出ac代码：

//注释的代码由于复杂度高不能过，但是一种参考
#include 
#define eps 1e-15
using namespace std;
/*struct p{
    int a,b;
    long long int v;
};*/
/*bool cmp(const p a, const p b){
    return a.v
int main()
{
    ios::sync_with_stdio(0);
    int n;
    long long int a[502][502];
/*    p p1[124752];*/
    //freopen("d://P1199_2.in", "r", stdin);
    cin>>n;
	for(int i=1;i<n;i++){
            a[i][i] = 0;
        for(int j=i+1;j<=n;j++){
                cin>>a[i][j];
                a[j][i] = a[i][j];
/*            cin>>p1[++k].v;
            p1[k].a=i;
            p1[k].b=j;*/
        }
	}
    //sort(p1+1,p1+1+k,cmp);
    long long int ans=0;
    for(int i = 1; i<=n; i++){
        sort(a[i]+1,a[i]+1+n);
        ans = max(ans,a[i][n-1]);
    }
    /*for(int i=k; i>=2; i--)
        for(int j=i-1; j>=1; j--)
        if((p1[i].a == p1[j].a || p1[i].a == p1[j].b || p1[i].b == p1[j].a || p1[i].b == p1[j].b) && p1[j].v > ans){ans = p1[j].v;break;}*/
    cout<<1<<endl<<ans;

    return 0;
}

删数问题
删除一位数，剩下的数位数已经确定了，如果想让它最小，则需删除高位的大数

#include 
#define eps 1e-15
using namespace std;
void solve(){

}

int main()
{
    string a;
    int k,i;
    cin>>a>>k;
    if(k>=a.size()){cout<<0;return 0;}
    while(k--){
            //找第一下降之前的数，删除它。

如果没有就删除最大的数，表现在循环上就是删除最后一个
        for(i=0; i<a.size()-1 && a[i]<=a[i+1]; i++);
        a.erase(i,1);
    }
    while(a.size()>1 && a[0]=='0'){
        a.erase(0,1);
    }
    cout<<a;
    return 0;
}

国王游戏
君王烽火戏诸侯只为博卿笑。

。

。

考虑最终最终状态的前一种状态，如何变成最终状态，设i为第i位大臣，j为第j位大臣，i < j，li，ri分别为大臣i的左右手数，lj，rj为大臣j的左右手数，k1为前i-1个大臣左手乘积，k2为i+1到j-1个大臣左手乘积。

不交换：
第i个大臣金币ans1=k1/ri。

第j个大臣ans2=k1*li*k2/rj;
交换：
第i个大臣金币ans3=k1*lj*k2/ri。

第j个大臣ans4=k1/rj;
ans=max(ans,ans1,ans2,ans3,ans4);
可知ans1<ans3;ans2>ans4;
ans=max(ans,ans3,ans4);
如果ans4>ans3可知li*ri > lj*rj,可得贪心策略li*ri < lj*rj;

//这里还用到了大精度乘法，除法，比较
#include 
#define eps 1e-15
using namespace std;
struct person{
    int l,r;
}p[10005];
string lc[10005],lr[10005];
void muti(string a, string b,int n){
    int len1=a.size(),len2=b.size(),x,aa[20005],bb[20005],t[20005];
    memset(aa,0,sizeof(aa));
    memset(bb,0,sizeof(bb));
    memset(t,0,sizeof(t));
    for(int i=1; i<=len1; i++)aa[i]=a[len1-i]-'0';
    for(int i=1; i<=len2; i++)bb[i]=b[len2-i]-'0';
    for(int i=1; i<=len1; i++){
        x=0;
        for(int j=1; j<=len2; j++){
            t[i+j-1]=aa[i]*bb[j]+x+t[i+j-1];
            x=t[i+j-1]/10;
            t[i+j-1]=t[i+j-1]%10;
        }
        t[i+len2]=x;
    }

    int len=len1+len2;
    while(t[len]==0 && len>1){
        len--;
    }
    for(int i=len; i>=1; i--){
//        cout<
        lc[n]+=char(t[i]+'0');

    }

}
void div(string a, int b,int n){
    int len1=a.size(),x=0,aa[20005],t[20005];
    memset(aa,0,sizeof(aa));
    memset(t,0,sizeof(t));
    for(int i=1; i<=len1; i++)aa[i]=a[i-1]-'0';
    for(int i=1; i<=len1; i++){
        t[i]=(x*10+aa[i])/b;
        x=(x*10+aa[i])%b;
    }
    int len=1;
    while(t[len]==0 && len<len1){
        len++;
    }
    for(int i=0; i<=len1-len; i++)
        lr[n]+=char(t[len+i]+'0');
}
bool cmp2(const person a, const person b){
    return a.l*a.r<b.l*b.r;
}
string compare(string a, string b){
    if(a.size()>b.size())return a;
    else if(a.size()<b.size())return b;
    else if(a>b)return a;
    else return b;
}
int main()
{
    //freopen("d://P1080_2.in","r",stdin);
    int n;cin>>n;
    for(int i=1; i<=n+1; i++)cin>>p[i].l>>p[i].r;
    sort(p+2,p+2+n,cmp2);
    lc[1]=to_string(p[1].l);
    string ans="0";
    for(int i=2; i<=n+1; i++){
        muti(lc[i-1],to_string( p[i].l ),i);
        div(lc[i-1],p[i].r,i);
        ans=compare(ans,lr[i]);
    }
    cout<<ans;
    return 0;
}