3 条题解
-
2
你说得对,但这个题也(?)可以用优先队列解决。
具体思路见注释#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; }时间复杂度 ,常数小,大概 50ms ,空间复杂度为 ,不像线段树卡线才能过。
当然这个题正解为单调队列+前缀和,时间复杂度为 ,但由于我的做法常数小,应该卡不掉
信息
- ID
- 927
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 225
- 已通过
- 12
- 上传者