首页 > 代码库 > BZOJ1577 USACO 2009 Feb Gold 1.Fair Shuttle Solution

BZOJ1577 USACO 2009 Feb Gold 1.Fair Shuttle Solution

2024-08-12 23:33:21   221人阅读

权限题，不给传送门啦！在学校OJ上交的..

 

有些不开心，又是一道贪心，又是一个高级数据结构的模板，又是看了别人的题解还写崩了QAQ，蒟蒻不需要理由呀。

 

正经题解：

首先，我们可以由「显然成立法」得出，只要我们按照右端点排序，然后能塞多少就塞多少就一定是最优哒！

 

你们可以YY一下，如果一堆牛能下车就赶紧下是不是可以得出最优的呢，我感觉不对但是他们都说对

 

然后就是很基本的线段树维护区间的查询和修改了。

需要注意的一个小地方是如果是线段树修改区间右端点是要-1的，这个很显然。

 

下面是具体实现：

技术分享
  1 //OJ 1623  2 //by Cydiater  3 //2016.9.10  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <string>  8 #include <algorithm>  9 #include <queue> 10 #include <map> 11 #include <ctime> 12 #include <cmath> 13 #include <cstdlib> 14 #include <iomanip> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=2e5+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 int K,N,C,x,y,v,ans=0; 28 struct SegTree{ 29     int delta,v; 30 }t[MAXN<<3]; 31 struct Query{ 32     int leftt,rightt,v; 33 }q[MAXN]; 34 namespace solution{ 35     inline bool cmp(Query a,Query b){return a.rightt==b.rightt?a.leftt>b.leftt:a.rightt<b.rightt;} 36     inline void downit(int node){ 37         t[node<<1].delta+=t[node].delta;t[node<<1|1].delta+=t[node].delta; 38         t[node<<1].v+=t[node].delta;t[node<<1|1].v+=t[node].delta; 39         t[node].delta=0; 40     } 41     void build(int leftt,int rightt,int root){ 42         if(leftt==rightt){ 43             t[root].delta=0;t[root].v=C; 44             return; 45         } 46         t[root].delta=0;t[root].v=C; 47         int mid=(leftt+rightt)>>1; 48         build(leftt,mid,root<<1); 49         build(mid+1,rightt,root<<1|1); 50     } 51     int get(int leftt,int rightt,int root){ 52         downit(root); 53         if(leftt>y||rightt<x)        return oo; 54         if(leftt>=x&&rightt<=y)        return t[root].v; 55         int mid=(leftt+rightt)>>1; 56         return min(get(leftt,mid,root<<1),get(mid+1,rightt,root<<1|1)); 57     } 58     void updata(int leftt,int rightt,int root){ 59         downit(root); 60         if(leftt>y||rightt<x)        return; 61         if(leftt>=x&&rightt<=y){ 62             t[root].delta-=v; 63             t[root].v-=v; 64             return; 65         } 66         int mid=(leftt+rightt)>>1; 67         updata(leftt,mid,root<<1); 68         updata(mid+1,rightt,root<<1|1); 69         t[root].v=min(t[root<<1].v,t[root<<1|1].v); 70     } 71     void init(){ 72         K=read();N=read();C=read(); 73         up(i,1,K){ 74             q[i].leftt=read();q[i].rightt=read()-1;q[i].v=read(); 75         } 76         sort(q+1,q+K+1,cmp); 77         build(1,N,1); 78     } 79     void slove(){ 80         up(i,1,K){ 81             x=q[i].leftt;y=q[i].rightt;v=q[i].v; 82             int num=get(1,N,1); 83             num=min(v,num); 84             if(num){ 85                 ans+=num;v=num; 86                 updata(1,N,1); 87             } 88         } 89     } 90     void output(){ 91         cout<<ans<<endl; 92     } 93 } 94 int main(){ 95     //freopen("input.in","r",stdin); 96     using namespace solution; 97     init(); 98     slove(); 99     output();100     return 0;101 }
View Code

 

BZOJ1577 USACO 2009 Feb Gold 1.Fair Shuttle Solution


联系
我们