70pts 求助!!!!!
查看原帖
70pts 求助!!!!!
547908
NightTide楼主2021/10/4 22:15

蒟蒻的第一道黑题,有没有大佬教一下我怎么改?

#include<bits/stdc++.h>
#define MAXN 1000010
#define INF 1000000000
using namespace std;
int t,n;
int len[MAXN];
void solve(void){
    deque<pair<int,int>> q1,q2;
    for(int i=1;i<=n;i++){
        q1.push_back({len[i],i});
    }
    int ans;
    while(true){
        if(q1.size()+q2.size()==2){
            ans=1;
            break;
        }
        pair<int,int> max_snake,min_snake;
        min_snake=q1.front(); q1.pop_front();
        if(q2.empty()){
            max_snake=q1.back(); q1.pop_back();
        }else if(q1.empty()){
            max_snake=q2.back(); q2.pop_back();
        }else{
            if(q1.back()>q2.back()){
                max_snake=q1.back(); q1.pop_back();
            }else{
                max_snake=q2.back(); q2.pop_back();
            }
        }
        pair<int,int> now_snake={max_snake.first-min_snake.first,max_snake.second};
        if(q1.empty()||q1.front()>now_snake){
            ans=q1.size()+q2.size()+2;
            for(int cnt=0;true;cnt++){
                if(q1.size()+q2.size()==1){
                    if(cnt%2) ans--;
                    break;
                }
                pair<int,int> max_snake;
                if(q2.empty()){
                    max_snake=q1.back(); q1.pop_back();
                }else if(q1.empty()){
                    max_snake=q2.back(); q2.pop_back();
                }else{
                    if(q1.back()>q2.back()){
                        max_snake=q1.back(); q1.pop_back();
                    }else{
                        max_snake=q2.back(); q2.pop_back();
                    }
                }
                now_snake={max_snake.first-now_snake.first,max_snake.second};
                if( !( (q1.empty()||now_snake<q1.front()) && (q2.empty()||now_snake<q2.front()) ) ){
                    if(cnt%2) ans--;
                    break;
                }
            }
            break;
        }else{
            q2.push_front(now_snake);
        }
    }
    printf("%d\n",ans);
}
int main(){
    scanf("%d",&t); t--;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&len[i]);
    }
    solve();
    while(t--){
        scanf("%d",&n);
        for(int i=1,u,v;i<=n;i++){
            scanf("%d%d",&u,&v);
            len[u]=v;
        }
        solve();
    }
}
2021/10/4 22:15
加载中...