题解 P3093 【[USACO13DEC]牛奶调度Milk Scheduling】

· · 题解

单纯的贪心，考虑到选择的问题，担心的就是前面的选择会不会对后面选择造成影响，所以我们换个方向考虑一下，也就是利用贪心思想了

我们按照加仑牛奶的价值进行一个排序，优先挤价值大的肯定是没错的，然后就是考虑，用哪一时间去挤得问题，这个其实也很好解决，因为每个时间点只能挤一头奶牛的奶，所以我们按照每个奶牛最后的选取时间往前找，尽量找到靠后面的时间不就可以了嘛

有没有觉得问题一下子豁然开朗了？

那么接下来的问题很简单定义结构体，按照牛奶价值给结构体排序。可能有点人还不是太会，我这里提供一个自己写的昂（dalao别笑）：

int cmp(love x,love y)
{
    return x.milk>y.milk;
}

剩下的就更简单了，循环到每一个奶牛，然后看看能否挤奶，能就加和，不能就跳过。

问题就这么解决了，下面上代码（只提供借鉴，不准复制粘贴）：

#include<bits/stdc++.h>//偷懒专用库 
#define ll long long
#define INF 15200
#define MAXN 99999//宏定义 
using namespace std;

inline int read(){
  char c=getchar();int x=0,f=1;
  while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
  return x*f;
}//这里是快读，可以提供借鉴，忽略掉也无所谓的 

struct love
{
    int milk;
    int time;
}you[INF];//定义一个机构体 

int cmp(love x,love y)
{
    return x.milk>y.milk;
}//结构体排序，按照加仑牛奶的价值从大到小排，先处理价值大的，保证不能挤得越小越好 

int n,ans,tot;
int a[INF];//判断这个时间点挤没有挤过奶 

int main()//主函数部分 
{
    n=read();//读入 
    for(int i=1;i<=n;++i)
      {
        you[i].milk=read();
        you[i].time=read();
      } //读入加仑牛奶价值和挤得最后时间 
    sort(you+1,you+1+n,cmp);//排序 
    for(int i=1;i<=n;++i)//判断是否能挤 
     {
        tot=0;//这是一个判断用的东西，待会就明白了 
        for(int j=you[i].time;j>=1;--j)//从他的最大时间开始，一直到一，看看有没有一个时间点没挤过 
         {
            if(a[j]==0)//如果这个点没挤过，就代表当前的牛奶可以被挤 
             {
                a[j]=1;//把这个点变成挤过 
                tot=1;//然后标记成挤过 
                break;//跳出循环 
             }//因为此时找到是最晚能挤的时间，所以不会影响以后的选择 
         }
        if(tot==1)
         ans+=you[i].milk;//如果标记过，证明奶挤过，所以答案加上价值 
     }
    cout<<ans;//输出
    return 0;//养成好习惯，从你我做起 
}

给蒟蒻一个赞吧，蒟蒻还没有赞呢