贪心法（二）：贪心法的应用例题

#include <stdio.h>
struct Milk
{
    int p,a;
};
int main()
{
    int n,m;
    scanf("%d%d",&n,&@H_304_1311@m);
    struct Milk a[5001];
    int i,j;
    for (i=0;i<m;i++)
        scanf("%d%d",&a[i].p,&a[i].a);
    for (i=0;i<m-1;i++)
        for (j=0;j<m-1-i;j++)
        {
           if (a[j].p>a[j+1].p)
           {
               struct Milk temp;
               temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;
           }
        }
    int ans=0;
    for (i=0;i<n;i++)
    {
        if (n>a[i].a)
        {
            ans+=a[i].p*a[i].a;
            n-=a[i].a;
        }
        else
        {
            ans+=a[i].p*n;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

#include <stdio.h>
int main()
{
   int m,s,c;
   scanf("%d%d%d",&m,&s,&c);
   int a[201],b[201];
   int i,j,t;
   for (i=1;i<=c;i++)
       scanf("%d",&a[i]);
   if (m>=C)
   {
       printf("%d\n",c);
       return 0;
   }
   for (i=1;i<c;i++)
     for (j=1;j<=c-i;j++)
        if (a[j]>a[j+1])
        {
           t=a[j];  a[j]=a[j+1];  a[j+1]=t;
        }
   int ans = a[c] - a[1] + 1;
   for (i=1;i<c;i++)
       b[i]=a[i+1]-a[i];
   for (i=1;i<c-1;i++)
     for (j=1;j<c-i;j++)
        if (b[j]<b[j+1])
        {
           t=b[j];  b[j]=b[j+1];  b[j+1]=t;
        }
   for(int i=1;i<m;i++)
   {
       ans=ans-b[i]+1;
   }
   printf("%d\n",ans);
   return 0;
}

#include <stdio.h>
#include <math.h>
struct Position
{
    int x,y;
};
struct Range
{
    double left,right;
};
int main()
{
    int n,d;
    scanf("%d%d",&n,&d);
    int flag=0;
    int i,j;
    struct Position pos[1001];
    struct Range dis[1001];
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&pos[i].x,&pos[i].y);
        if (d>=pos[i].y)
        {
            double dd=sqrt(d*d-pos[i].y*pos[i].y);
            dis[i].left=pos[i].x-dd;
            dis[i].right=pos[i].x+dd;
        }
        else
            flag=1;
    }
    if (flag)
        printf("-1\n");
    else
    {
        for (i=0;i<n-1;i++)
            for (j=0;j<n-1-i;j++)
               if (dis[j].right>dis[j+1].right)
               {
                   struct Range temp;
                   temp=dis[j]; dis[j]=dis[j+1]; dis[j+1]=temp;
               }
        int cnt=1;
        double finish=dis[0].right;
        for (i=1;i<n;i++)
        {
            if (dis[i].left>finish)
            {
               cnt++;
               finish=dis[i].right;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

#include <stdio.h>
struct node
{
    int b,e,t;
};
int main()
{
    int n;
    scanf("%d",&n);
    struct node a[1001],temp;
    int i,j;
    for (i=0;i<n;i++)
        scanf("%d%d%d",&a[i].b,&a[i].e,&a[i].t);
    for (i=0;i<n-1;i++)
       for (j=0;j<n-1-i;j++)
          if (a[j].e>a[j+1].e || (a[j].e==a[j+1].e && a[j].b<a[j+1].b))
          {
             temp=a[j];  a[j]=a[j+1];  a[j+1]=temp;
          }
    int b[1001]={0};
    int ans=0;
    for (i=0;i<n;i++)
    {
        int sum=0;
        for (j=a[i].b;j<=a[i].e;j++)
            sum+=b[j];
        for (j=a[i].e;j>=a[i].b && sum<a[i].t;j--)
        {
            if (b[j]!=1)
            {
                b[j]=1;
                sum++;
                ans++;
            }
        }
    }
    printf("%d\n",ans);
      return 0;
}