题解 P1607 【[USACO09FEB]庙会班车Fair Shuttle】

· · 题解

题意是给你几堆奶牛，每个奶牛都有想去的地方，给你一个汽车，汽车有一个容量和固定的行走路线，询问最多能搭载的奶牛的数量。

我们来考虑一种贪心的思想，按右端点从小到大排一遍序，为什么呢？后面说，然后对排好序的每堆奶牛依次进行遍历，如果当前有空位，空位大于这堆奶牛的数量，那就全上去，不然的话，就能上去几个就上去几个。这样下来的话，结果一定是最优的，其正确性不难证明，因为刚开始我们对每堆奶牛要到的地方从小到大排了序(即终点)，那么每个位置最多只有一次奶牛上车，而且这些奶牛来自同一群，所以我们对每堆奶牛分别进行考虑即可，这就是为什么要按右端点排序的原因。贪心过程中，要维护最大值。因为要算最少的空位子，下面给出两种代码：

1、纯贪心&贪心：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 50007
using namespace std;
int ans,n,m,k,w[maxn];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int u,v,c;
}e[maxn];
const int inf=0x7fffffff;
inline bool cmp(node a, node b) {
  if(a.v!=b.v) return a.v<b.v;
  return a.u<b.u;
}
int main() {
  k=qread(),n=qread(),m=qread();
  for(int i=1;i<=k;++i) e[i].u=qread(),e[i].v=qread(),e[i].c=qread();
  sort(e+1,e+1+k,cmp);
  for(int i=1;i<=k;++i) {
    if(w[e[i].u]>=m) continue;
    int minn=inf;
    for(int j=e[i].u;j<=e[i].v;++j) {
      minn=min(m-w[j],minn);
      if(minn<=0) break;
    }
    if(minn>0) {
      if(minn>=e[i].c) { 
        for(int j=e[i].u;j<e[i].v;++j)
          w[j]+=e[i].c;
        ans+=e[i].c;
      }
      else {
        for(int j=e[i].u;j<e[i].v;++j)
          w[j]+=minn;
        ans+=minn;
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

2、线段树&贪心&排序：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 20007
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int inf=0x7fffffff;
int n,k,m,maxx[maxn<<2],lazy[maxn<<2],zrj,w[50007];
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int u,v,c;
}e[50007];
inline bool cmp(node a, node b) {
  if(a.v!=b.v) return a.v<b.v;
  return a.u<b.u;
}
inline void pushup(int rt) {
  maxx[rt]=max(maxx[ls],maxx[rs]);
}
inline void pushdown(int rt) {
  if(lazy[rt]) {
    maxx[ls]+=lazy[rt],lazy[ls]+=lazy[rt];
    maxx[rs]+=lazy[rt],lazy[rs]+=lazy[rt];
    lazy[rt]=0;
  }
}
void modify(int rt, int l, int r, int L, int R, int val) {
  if(L>r||R<l) return;
  if(L<=l&&r<=R) {
    lazy[rt]+=val,maxx[rt]+=val;
    return;
  }
  int mid=(l+r)>>1;
  pushdown(rt);
  modify(ls,l,mid,L,R,val),modify(rs,mid+1,r,L,R,val);
  pushup(rt);
}
int cmax(int rt, int l, int r, int L, int R) {
  if(L>r||R<l) return -inf;
  if(L<=l&&r<=R) return maxx[rt];
  int mid=(l+r)>>1,ans=-inf;
  pushdown(rt);
  if(L<=mid) ans=max(ans,cmax(ls,l,mid,L,R));
  if(R>mid) ans=max(ans,cmax(rs,mid+1,r,L,R));
  return ans;
}
int main() {
  k=qread(),n=qread(),m=qread();
  for(int i=1;i<=k;++i) e[i].u=qread(),e[i].v=qread(),e[i].c=qread();
  sort(e+1,e+1+k,cmp);
  for(int i=1;i<=k;++i) {
    int p=cmax(1,1,n,e[i].u,e[i].v-1);
    int minn=min(m-p,e[i].c);
    zrj+=minn,w[i]+=minn;
    modify(1,1,n,e[i].u,e[i].v-1,w[i]);
  }
  printf("%d\n",zrj);
  return 0;
}

希望这篇题解对大家能有所帮助。