Codeforces Round #552 (Div. 3)D、E题解

￡神魔★判官ぃ 2022-01-12 08:19 183阅读 0赞

# D. Walking Robot #

## 题意 ##

机器人在一维坐标轴上从0走到x，中途可以在有光的地方可以选择给太阳能电池充电，每次移动都要消耗一单位电，蓄电池容量为a，太阳能电池容量为b，一开始都是满电，问机器人采取最佳策略最多可以走多远。

## 题解 ##

直接贪心模拟即可，具体见代码注释

#  E. Two Teams #

## 题意 ##

两个人轮流取最大值与旁边k个数，问最后这所有的数分别被谁给取走了。

## 题解 ##

线段树维护总区间最大值，取走数相当于更新对应区间最大值为0，注意暴力更新答案会T，有一个比较取巧的方法是提前算一下部分数的离他最远的连续被取走的数的位置，然后在更新答案的时候就可以一次跳远一点，我之前就是因为一步一步跳T37了。

1 #define dbg(x) cout<<#x<<" = "<< (x)<< endl
      2 #define IO std::ios::sync_with_stdio(0);
      3 #include <bits/stdc++.h>
      4 #define iter ::iterator
      5 using namespace  std;
      6 typedef long long ll;
      7 typedef pair<ll,ll>P;
      8 #define pb push_back
      9 #define se second
     10 #define fi first
     11 #define rs o<<1|1
     12 #define ls o<<1
     13 const ll inf=0x7fffffff;
     14 const int N=2e5+10;
     15 int n,x,y;
     16 int a[N],b[N],c[N];
     17 int maxv[N*4],lazy[N*4];
     18 void push(int o){
     19     maxv[o]=max(maxv[ls],maxv[rs]);
     20 }
     21 void down(int o){
     22     if(lazy[o]){
     23         maxv[o]=0;
     24         lazy[ls]=lazy[rs]=1;
     25         maxv[ls]=maxv[rs]=0;
     26     }
     27 }
     28 void build(int o,int l,int r){
     29     if(l==r){
     30         cin>>maxv[o];
     31         return;
     32     }
     33     int m=(l+r)/2;
     34     build(ls,l,m);
     35     build(rs,m+1,r);
     36     push(o);
     37 }
     38 void up(int o,int l,int r,int ql,int qr){
     39     if(l>=ql&&r<=qr){
     40         maxv[o]=0;
     41         lazy[o]=1;
     42         return;
     43     }
     44     down(o);
     45     int m=(l+r)/2;
     46     if(ql<=m)up(ls,l,m,ql,qr);
     47     if(qr>m)up(rs,m+1,r,ql,qr);
     48     push(o);
     49 }
     50 int qu(int o,int l,int r){
     51     if(l==r){
     52         return l;
     53     }
     54     down(o);
     55     int m=(l+r)/2;
     56     if(maxv[ls]==maxv[1]){
     57         return qu(ls,l,m);
     58     }
     59     else return qu(rs,m+1,r);
     60 }
     61 int k;
     62 int main(){
     63     IO;
     64     cin>>n>>k;
     65     build(1,1,n);
     66     int g=0;
     67     for(int i=1;i<=n;i++){
     68         b[i]=c[i]=i;
     69     }
     70     while(1){
     71         if(maxv[1]==0)break;
     72         g++;
     73         int h=g%2?1:2;
     74         int p=qu(1,1,n);
     75         int ql=0,qr=n+10;
     76         for(int i=p,cnt=0;i>=1&&cnt<=k;i--){
     77             ql=i;
     78             i=c[i];  
     79             if(a[i]!=0)continue;
     80             a[i]=h;
     81             cnt++;
     82                      
     83         }
     84         for(int i=p+1,cnt=1;i<=n&&cnt<=k;i++){
     85             qr=i;
     86             i=b[i];
     87             if(a[i]!=0)continue;
     88             a[i]=h;
     89             cnt++;
     90             
     91         }
     92         for(int i=ql;i<=min(ql+10,qr);i++){
     93             b[i]=qr;
     94         }
     95         for(int i=qr;i>=max(qr-10,ql);i--){
     96             c[i]=ql;
     97         }
     98         up(1,1,n,max(1,ql),min(qr,n));
     99     }
    100     for(int i=1;i<=n;i++)cout<<a[i];
    101 }

转载于:https://www.cnblogs.com/ccsu-kid/p/10723471.html