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 ,空间复杂度为 ,不像线段树卡线才能过。
当然这个题正解为单调队列+前缀和,时间复杂度为 ,但由于我的做法常数小,应该卡不掉 -
1
破环成链,复制一倍数组。直接线段树维护以 为起点到达每一个点的时候加好油走到下一个点之后的油量,查询区间内这一值的最小值,如果最小值为负,则一定不可。换起点时直接使用前缀和推出其新值即可。注意正反分别扫一遍。 另外,空间时间均卡线,跑慢勿笑。
#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; }
- 1
信息
- ID
- 927
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 225
- 已通过
- 12
- 上传者