CF2018B Speedbreaker
被*1900狠狠杀掉了麻麻，S组即将来临我真的没救了。。。。
考虑无解的情况，对于每一个时间 \(t\)，找到能够包含所有 \(a_i\) 满足 \(a_i\leq t\) 的区间 \([l_t,r_t]\)，意思就是在 \(t\) 的时间里必须把这一段区间全走完才能保证走完了每一个 \(a_i\leq t\)，那么如果这样的一段区间 \(r_t-l_t+1>t\) 则绝壁不可以走完，此时答案为0。
考虑何时可以有答案，假如从某一个点 \(x\) 出发，那么相当于使得 \(a_x=1\)，因为点 \(x\) 绝壁包含在每一个 \(t\) 的区间内。那么就要对于每一个 \(t\) 满足把 \(x\) 算进去以后的长度仍然满足条件，有三种情况即 \(x\) 在左在右在中间。
- 在左：满足 \(r_t-x+1\leq t\longrightarrow r_t-t+1\leq x\)
- 在右：满足 \(x-l_t+1\leq t\longrightarrow x\leq l_t+t-1\)
- 中间：自动满足
综合一下直接得到 \(x\) 的取值必定在区间 \([r_t-t+1,l_t+t-1]\) 之间，对于每一个 \(t\) 的该区间取一下交集即可。
怎么做！！！！
直接按照 \(a_i\) 从小到大的顺序访问然后扩展区间然后算出来以后交一下即可。
贴代码！！！！
#include <bits/stdc++.h>
using namespace std;
int n,t,a[200010],id[200010],pl,pr,ansl,ansr;
bool cmp(int x,int y)
{return a[x] < a[y];
}
int main()
{cin >> t;while(t--){cin >> n; bool chk = 0; ansl = 1; ansr = n;for (int i = 1;i <= n ;i++) cin >> a[i];for (int i = 1;i <= n;i++) id[i] = i;sort(id+1,id+n+1,cmp);pl = pr = id[1];for (int i = 1,cnt = 1;i <= n;i++){bool f = 0;while(cnt <= n && a[id[cnt]] <= i){pl = min(id[cnt],pl); pr = max(id[cnt],pr);if (a[id[cnt]] == i) f = 1; cnt++;}if (!f) continue;if (pr-pl+1 > i){chk = 1;break;}ansl = max(ansl,pr-i+1); ansr = min(ansr,pl+i-1);}if (ansl > ansr) chk = 1;if (chk) cout << "0\n";else cout << ansr-ansl+1 << "\n";}return 0;
}
CSP-S第二轮决一死战了决一死战
愿星族与我同在
May Star Clan be with me