3 条题解

  • 2
    @ 2026-10-21 10:46:17

    你说得对,但这个题也(?)可以用优先队列解决。
    具体思路见注释

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+55;
    const int M=N*2;
    int p[M],d[M],n;
    bool f[M];//顺时针是否可以 
    bool ff[M];//逆时针是否可以 
    struct node{
    	int id; 
    	int x;//第 id 个地点开始的油量 
    };
    node makenode(int x,int y){//数字转结构体 
    	node aa;
    	aa.x=x; aa.id=y;
    	return aa;
    }
    bool operator < (node a,node b){//优先队列需要重载运算符 < 
    	return a.x<b.x;
    }
    priority_queue<node> pq;//顺时针 
    priority_queue<node> pq2;//逆时针 
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
    //	考虑转化,只顺时针跑一遍 + 逆时针跑一遍 
    //	对于每个地点,若此时油量 < 第 y 个地点开始时的油量, 
    //	则第 y 个地点无法作为开头 
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>p[i]>>d[i];
    		p[i+n]=p[i];//破环成链 
    		d[i+n]=d[i];
    	}
    	int x=0;//初始化当前油量为 0 
    	for(int i=1;i<=n*2;i++){//顺时针 1 -> 2n 
    		pq.push(makenode(x,i));//将这个点加入优先队列 
    		x+=p[i];
    		x-=d[i];
    		node y=pq.top();
    		while(y.x>x&&!pq.empty()){//如果现在的油量小于某个点开始时的油量,则这个点不行 
    			pq.pop();
    			f[y.id]=1;
    			y=pq.top();
    		}
    	}
    	x=0;//初始化 
    	for(int i=n*2;i>=1;i--){//逆时针 2n -> 1
    		pq2.push(makenode(x,i-n));//将这个点加入优先队列 
    		x+=p[i];
    		x-=d[i-1];
    		node y=pq2.top();
    		while(y.x>x&&!pq2.empty()){//同理 
    			pq2.pop();
    			ff[max(y.id,0ll)]=1;//防止 RE 
    			y=pq2.top();
    		}
    		//由于 
    	}
    	for(int i=1;i<=n;i++){
    		if(f[i]&&ff[i]) cout<<"NO"<<'\n';
    		//只有当顺时针,逆时针都不行时才是 NO 
    		else cout<<"YES"<<'\n';
    		//否则为 YES 
    	}
    	return 0;
    }
    

    时间复杂度 O(Nlog⁡N)O(N\log N),常数小,大概 50ms ,空间复杂度为 O(N)O(N) ,不像线段树卡线才能过。
    当然这个题正解为单调队列+前缀和,时间复杂度为 O(N)O(N),但由于我的做法常数小,应该卡不掉

    AC记录

    信息

    ID
    927
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    225
    已通过
    12
    上传者