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记录

    • 1
      @ 2026-10-20 18:08:04

      破环成链,复制一倍数组。直接线段树维护以 11 为起点到达每一个点的时候加好油走到下一个点之后的油量,查询区间内这一值的最小值,如果最小值为负,则一定不可。换起点时直接使用前缀和推出其新值即可。注意正反分别扫一遍。 另外,空间时间均卡线,跑慢勿笑。

      #include <bits/stdc++.h>
      #define int long long
      using namespace std;
      const int N = 1e6 + 5;
      const long long INF = 1e18;
      int n, p[N << 1], d[N << 1];
      int sp[N << 1], sd[N << 1];
      struct tree {
      	int l, r;
      	long long val;
      }tr[N << 3];
      void pushup(int u) {
      	tr[u].val = min(tr[u << 1].val, tr[u << 1 | 1].val);
      } 
      void build(int u, int l, int r) {
      	tr[u].l = l, tr[u].r = r;
      	if(l == r) {
      		tr[u].val = INF;
      		return ;
      	}
      	int mid = (l + r) >> 1;
      	build(u << 1, l, mid);
      	build(u << 1 | 1, mid + 1, r);
      	pushup(u);
      }
      void update(int u, int p, long long x) {
      	if(tr[u].l == tr[u].r) {
      		tr[u].val = x;
      		return ;
      	}
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(p <= mid) update(u << 1, p, x);
      	else update(u << 1 | 1, p, x);
      	pushup(u);
      }
      long long query(int u, int l, int r) {
      	if(tr[u].l >= l && tr[u].r <= r) {
      		return tr[u].val;
      	}
      	if(tr[u].l > r || tr[u].r < l || l > r) return INF;
      	int mid = (tr[u].l + tr[u].r) >> 1;
      	if(r <= mid) return query(u << 1, l, r);
      	if(l > mid) return query(u << 1 | 1, l, r);
      	return min(query(u << 1, l, r), query(u << 1 | 1, l, r));
      }
      bool mark[N];
      signed main() {
      	ios :: sync_with_stdio(0);
      	cin.tie(0);
      	cout.tie(0);
      	cin >> n;
      	for(int i=1; i<=n; ++i) {
      		cin >> p[i] >> d[i];
      		p[i + n] = p[i], d[i + n] = d[i];
      	}
      	build(1, 1, n << 1);
      	for(int i=1; i<=2*n; ++i) {
      		sp[i] = sp[i - 1] + p[i];
      		sd[i] = sd[i - 1] + d[i];
      		update(1, i, sp[i] - sd[i]);
      	}
      	for(int i=1; i<=n; ++i) {
      		int L = i, R = i + n - 1;
      		long long res = query(1, L, R);
      		if(res - sp[i - 1] + sd[i - 1] < 0) mark[i] = 0;
      		else mark[i] = 1;
      	}
      	build(1, 1, n << 1);
      	for(int i=2*n; i>=1; --i) {
      		sp[i] = sp[i + 1] + p[i];
      		sd[i] = sd[i + 1] + d[i];
      		update(1, i, sp[i + 1] - sd[i]);
      	}
      	for(int i=2*n; i>=1+n; --i) {
      		int L = i - n, R = i - 1;
      		long long res = query(1, L, R);
      		if(res - sp[i + 1] + sd[i] >= 0) mark[i - n] = 1;
      	}
      	for(int i=1; i<=n; ++i) {
      		if(mark[i]) cout << "YES\n";
      		else cout << "NO\n";
      	}
      	return 0;
      }
      
      • @ 2026-10-21 10:40:06

        caohongxuan,a题数据更新了,你去试试

      • @ 2026-10-21 10:52:45

        过了

    • 0
      @ 2026-10-21 15:53:52

      loj 10178 旅行问题

      • 1

      信息

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