D. Walking Robot

題意

機器人在一維坐標軸上從0走到x，中途可以在有光的地方可以選擇給太陽能電池充電，每次移動都要消耗一單位電，蓄電池容量為a，太陽能電池容量為b，一開始都是滿電，問機器人采取最佳策略最多可以走多遠。

題解

直接貪心模擬即可，具體見代碼注釋

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=3e5+10; 15 int n,x,y; 16 int a[N]; 17 int main(){ 18 IO; 19 cin>>n>>x>>y; 20 int tx=x,ty=y; 21 for(int i=1;i<=n;i++){ 22 cin>>a[i]; 23 } 24 int ans=0; 25 for(int i=1;i<=n;i++){ 26 if(a[i]){//如果有光 27 if(x>0){//如果蓄電池有電 28 if(y==ty){//如果太陽能電池充滿優先用太陽能電池 29 y--; 30 } 31 else{ 32 x--; 33 if(y<ty)y++; 34 } 35 } 36 else{ 37 if(y==0)break;//如果蓄電池沒電太陽能電池也沒電 38 y--; 39 } 40 } 41 else{//無光 42 if(y>0)y--;//如果太陽能電池有電優先用太陽能電池 43 else{ 44 if(x==0)break;//如果蓄電池沒電太陽能電池也沒電 45 x--; 46 } 47 } 48 ans++; 49 } 50 cout<<ans<<endl; 51 }

?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

總結

以上是生活随笔為你收集整理的Codeforces Round #552 (Div. 3)D、E题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。