正文 

当前位置： 首页 > java > java教程

[usaco2009feb]庙会捷运fairshuttle

Wolfycz Wolfycz     2022-10-13     385

关键词：

Description
公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.

他们希望从Si到Ei去。
公交车只能座C（1<=C<=100）只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛听要求。
注意：对于每一群奶牛，可以部分满足，也可以全部满足，也可以全部不满足。

Input
第1行： 三个整数： K，N，C。 由空格隔开。

第2..K+1行：第i+1行，告诉你第i组奶牛的信息： S_i, E_i and M_i。由空格隔开。

Output
一行：可以在庙会乘坐捷运的牛的最大头数

Sample Input
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

Sample Output
10

HINT
公交车可以把2头奶牛从展台1送到展台5，3头奶牛从展台5到展台8， 2头奶牛从展台8 到展台14，1头奶牛从展台9送到展台12，一头奶牛从展台13送到展台14， 一头奶牛从 14送到15。

这个题目的贪心思想显而易见，我们肯定要让下车早的奶牛上车，其次就是上车晚的。然后如何判断能上多少奶牛呢？用线段树记录每个时间点，车上还有多少空位，然后大力维护一波就可以了

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for (;ch<‘0‘||ch>‘9‘;ch=getchar())  if (ch==‘-‘)    f=-1;
    for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar())   x=(x<<3)+(x<<1)+ch-‘0‘;
    return x*f;
}
inline void print(int x){
    if (x>=10) print(x/10);
    putchar(x%10+‘0‘);
}
const int N=5e4,M=2e4;
int n,m,K;
int root=1;
struct AC{
    int l,r,val;
    void join(int x,int y,int z){l=x,r=y,val=z;}
    bool operator <(const AC &x)const{return r!=x.r?r<x.r:l>x.l;}
}A[N+10];
struct Tree{
    #define ls (p<<1)
    #define rs ((p<<1)|1)
    int Min[M*16+10],lazy[M*16+10];
    void updata(int p){Min[p]=min(Min[ls],Min[rs]);}
    void pushdown(int p){//“懒惰”标记
        if (!lazy[p])   return;
        lazy[ls]+=lazy[p];
        lazy[rs]+=lazy[p];
        Min[ls]+=lazy[p];
        Min[rs]+=lazy[p];
        lazy[p]=0;
    }
    void build(int p,int l,int r){
        if (l==r){Min[p]=K;return;}//开始空位为K
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        updata(p);
    }
    int get(int p,int l,int r,int x,int y){
        pushdown(p);
        if (x<=l&&r<=y) return Min[p];
        int mid=(l+r)>>1,ans1=inf,ans2=inf;
        if (x<=mid) ans1=get(ls,l,mid,x,y);
        if (y>mid)  ans2=get(rs,mid+1,r,x,y);
        if (ans1==inf&&ans2==inf)   return 0;
        return min(ans1,ans2);
    }
    void change(int p,int l,int r,int x,int y,int t){
        pushdown(p);
        if (x<=l&&r<=y){Min[p]+=t,lazy[p]+=t;return;}
        int mid=(l+r)>>1;
        if (x<=mid) change(ls,l,mid,x,y,t);
        if (y>mid)  change(rs,mid+1,r,x,y,t);
        updata(p);
    }
}T;
int main(){
    n=read(),m=read(),K=read();
    int ans=0;
    for (int i=1,x,y,z;i<=n;i++)    x=read(),y=read()-1,z=read(),A[i].join(x,y,z);//因为在时刻r奶牛已经下车了，所以右端点要--
    sort(A+1,A+1+n);
    T.build(1,1,m);
    for (int i=1;i<=n;i++){
        int l=A[i].l,r=A[i].r;
        int tmp=min(A[i].val,T.get(1,1,m,l,r));//看看能上多少奶牛，上不了的就干脆别上了（不是vip不能挤上车）
        if (tmp)    T.change(1,1,m,l,r,-tmp),ans+=tmp;//更新，包括答案的更新和线段树的更新
    }
    printf("%d
",ans);
    return 0;
}

bzoj1577:[usaco2009feb]庙会捷运fairshuttle

n<=20000个车站，车能同时载C<=100个人，求能满足K<=50000群人的多少个。每群人给起点终点和人数，一群人不一定要都满足。一开始想DP，想不出，很菜。贪心即可。如果有右端点相同的几群人，那肯定优先满足左端点大的；... 查看详情

贪心bzoj1577:[usaco2009feb]庙会捷运fairshuttle(代码片段)

一类经典的线段贪心Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）... 查看详情

bzoj1577:[usaco2009feb]庙会捷运fairshuttle——小根堆+大根堆+贪心

Description公交车一共经过N（1<=N<=20000）个站点，从站点1一直驶到站点N。K（1<=K<=50000)群奶牛希望搭乘这辆公交车。第i群牛一共有Mi（1<=Mi<=N)只.他们希望从Si到Ei去。公交车只能座C（1<=C<=100）只奶牛。而且不走重... 查看详情

洛谷p1607[usaco09feb]庙会班车fairshuttle

P1607[USACO09FEB]庙会班车FairShuttle题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohel 查看详情

p1607[usaco09feb]庙会班车fairshuttle

题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohelpthemenjoythefair,FJhasarrangedf 查看详情

洛谷p1607[usaco09feb]庙会班车fairshuttle

题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohelpthemenjoythefair,FJhasarrangedf 查看详情

[usaco09feb]庙会班车fairshuttle

题目描述逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代... 查看详情

usaco2009febfairshuttle庙会班车贪心(代码片段)

题目题目描述AlthoughFarmerJohnhasnoproblemswalkingaroundthefairtocollectprizesorseetheshows,hiscowsarenotinsuchgoodshape;afulldayofwalkingaroundthefairleavesthemexhausted.Tohelpthemenjoythefair,FJhasarrange 查看详情

bzoj1579[usaco2009feb]revampingtrails道路升级

1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit:10SecMemoryLimit:64MBSubmit:2343Solved:666[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接 查看详情

bzoj1579:[usaco2009feb]revampingtrails道路升级dijkstra,堆,分层图

1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 1573  Solved: 428[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的 查看详情

bzoj1579:[usaco2009feb]revampingtrails道路升级

1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec  MemoryLimit: 64MBDescription每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i 查看详情

[bzoj3398][usaco2009feb]bullcow牡牛和牝牛（动态规划）

3398:[Usaco2009Feb]Bullcow牡牛和牝牛TimeLimit: 1Sec  MemoryLimit: 128MBSubmit: 235  Solved: 159[Submit][Status][Discuss]Description    约翰要带N(1≤N≤ 查看详情

bzoj1579:[usaco2009feb]revampingtrails道路升级优先队列+dij

1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec  MemoryLimit: 64MBSubmit: 1768  Solved: 481[Submit][Status][Discuss]Description每天,农夫John需要经过一些道路去检查牛棚N里面的 查看详情

[usaco2009feb]stockmarket股票市场完全背包

Code:#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<stack>#include<string>usingnamespacestd;voidsetIO(stringa)freopen((a+".in").c_s 查看详情

bzoj15791579:[usaco2009feb]revampingtrails道路升级（最短路）

1579:[Usaco2009Feb]RevampingTrails道路升级Description每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i<=N;1<=P2_i<=N).John需要T_i(1<=T_i<=1,000, 查看详情

bzoj1579:[usaco2009feb]revampingtrails道路升级--分层图最短路

1579:[Usaco2009Feb]RevampingTrails道路升级TimeLimit: 10Sec  MemoryLimit: 64MBDescription每天,农夫John需要经过一些道路去检查牛棚N里面的牛.农场上有M(1<=M<=50,000)条双向泥土道路,编号为1..M.道路i连接牛棚P1_i和P2_i(1<=P1_i 查看详情

bzoj1579[usaco2009feb]revampingtrails道路升级

堆优化的dijkstra。把一个点拆成k个。日常空间要开炸一次。。//Twenty#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<queue>#include<vector>t 查看详情

bzoj1578:[usaco2009feb]stockmarket股票市场

【题意】给定s个股票和d天，给出价格矩阵s*d，每天可以买入或卖出整数倍股票，初始资金m，求最大利益。m<=200000,s<=50,d<=10。【算法】完全背包【题解】关键在于转化：第一天买入-第三天卖出，相当于，第一天买入-第二... 查看详情