贪心算法

57 阅读 0 评论 38 点赞

我是靠谱客的博主幸福彩虹，最近开发中收集的这篇文章主要介绍贪心算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

HDU 1009 FatMouse’ Trade
策略：每次选择性价比最高的商品进行购买

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct goods{
    double weight;
    double value;
    double s;
    bool operator < (const goods & A){
        return s>A.s;
    }
}buf[1000];
int main()
{
    double m;
    int n;
    while(scanf("%lf%d",&m,&n)!=EOF){
        if(m==-1&&n==-1) break;
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&buf[i].weight,&buf[i].value);
            buf[i].s=buf[i].weight/buf[i].value;
        }
    sort(buf,buf+n);
    int dx=0;
    double ans=0;
    while(m>0&&dx<n){
        if(m>buf[dx].value){
            ans+=buf[dx].weight;
            m-=buf[dx].value;
        }
        else {
            ans+=buf[dx].weight*m/buf[dx].value;
            m=0;
        }
        dx++;
    }
    printf("%.3lfn",ans);
    }
    return 0;
}

HDU1050 Moving Tables
解法一：
直接计算需要搬运次数最多的走廊

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 202
int main()
{
    int t;
    scanf("%d",&t);
    int count1[N];
    while(t--){
        int n;
        scanf("%d",&n);
        memset(count1,0,sizeof(count1));
        for(int i=0;i<n;i++){
            int beginroom,endroom;
            scanf("%d%d",&beginroom,&endroom);
            if(beginroom>endroom) swap(beginroom,endroom);
            for(int j=(beginroom-1)/2;j<=(endroom-1)/2;j++)
                count1[j]++;
        }
        int cmax = count1[0];
		for (int i =1; i<N; ++i)
			if (count1[i]>cmax)
				cmax = count1[i];
        printf("%dn",10*cmax);
    }
    return 0;
}

解法二
策略：每次选择尽可能多的区间进行搬运

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
    int head,tail,flag;
    bool operator < (const node &A){
        return head<A.head;
    }
}road[200];
int main()
{
    int t,n,tail,cnt;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cnt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&road[i].head,&road[i].tail);
            //预处理， 把房间号对应到门前的栈道号
            road[i].head=(road[i].head+1)/2;
            road[i].tail=(road[i].tail+1)/2;
            if(road[i].head>road[i].tail)
            swap(road[i].head,road[i].tail);
            road[i].flag=0;
        }
        sort(road,road+n);  //使得头位置靠近，每一次能够装下得区间数更多
        for(int i=0;i<n;i++)
        {
            if(!road[i].flag)
            {
                road[i].flag=1;
                tail=road[i].tail;
                for(int j=i+1;j<n;j++)
                {
                    if(!road[j].flag && road[j].head>tail)  //本条信息没被用过并且合法
                    {
                        road[j].flag=1;
                        tail=road[j].tail;
                    }
                }
                cnt++;
            }
        }
        cout<<cnt*10<<endl;
    }
    return 0;
}

HDU1052 田忌赛马
策略：1.当田忌最慢的马比齐王最慢的马快，赢一场先
2.当田忌最慢的马比齐王最慢的马慢，和齐王最快的马比，输一场
3.当田忌最快的马比齐王最快的马快时，赢一场先。
4.当田忌最快的马比齐王最快的马慢时，拿最慢的马和齐王最快的马比，输一场。
5.当田忌最快的马和齐王最快的马相等时，拿最慢的马来和齐王最快的马比.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1005
int t[N],k[N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n){
        for(int i=0; i<n; i++)
            scanf("%d",&t[i]);
        for(int i=0; i<n; i++)
            scanf("%d",&k[i]);
        sort(t,t+n);
        sort(k,k+n);
        int t_max,k_max,t_min,k_min;
        t_max=k_max=n-1;
        t_min=k_min=0;
        int sum=0;
        while(t_min<=t_max&&k_min<=k_max)
        {
             if(t[t_max]>k[k_max])
            {
                sum+=200;
                t_max--;
                k_max--;
            }
            else if(k[k_max]>t[t_max])
            {
                sum-=200;
                t_min++;
                k_max--;
            }
            else
            {
                if(t[t_min]>k[k_min])
                {
                    sum+=200;
                    t_min++;
                    k_min++;
                }
                else if(t[t_min]<k[k_min])
                {
                    sum-=200;
                    t_min++;
                    k_max--;
                }
                else
                {
                    if(t[t_min] < k[k_max])
                        sum-=200;
                    t_min++;
                    k_max--;
                }
            }
        }
        printf("%dn",sum);
    }
    return 0;
}

POJ3617 Best Cow Line
策略：每次从首位和末位中选取小者输出，如果首位和末位元素相等，则通过比较两者的下一位元素，若相等则继续循环直至不相等，然后再对start和end进行操作

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 2005
int n;
char str[N];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
       scanf(" %c",&str[i]);
    }
    int cnt=0;
    int a=0,b=n-1;
    //这个循环超级巧妙，如果遇到相同的则从当前位置往后找到不同的，但是l和r值并未改变，所以还是原来的位置
    while(a<=b)
    {
        bool left=false;//判断是在l还是r需要移动
        for(int i=0;a+i<=b;i++)
        {
            if(str[a+i]<str[b-i])
            {
                left=true;
                cnt++;
                break;
            }
            else if(str[a+i]>str[b-i])
            {
                cnt++;
                left=false;
                break;
            }
        }
        if(left)putchar(str[a++]);
        else putchar(str[b--]);
        if(cnt % 80 ==0)
        {
            printf("n");
        }
    }
    return 0;
}

POJ 3069 Saruman’s Army
策略：每次尽可能选择距离比较远的点添加标记

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 20005
int x[N];
int main()
{
    int r,n;
    while(scanf("%d%d",&r,&n)!=EOF){
        if(r==-1&&n==-1) break;
        for(int i=0;i<n;i++){
            scanf("%d",&x[i]);
        }
        sort(x,x+n);
        int cur=0,ans=0;
		while(cur<n)
		{
			int s=x[cur++];//s表示没有被覆盖的最左边的点
			while(cur<n&&x[cur]<=s+r)//一直向右前进直到距s的距离大于R的点
				cur++;
			int p=x[cur-1];//被标记的点
			while(cur<n&&x[cur]<=p+r)//一直向右前进直到距p的距离大于R的点
				cur++;
			ans++;
		}
		printf("%dn",ans);
    }
    return 0;
}