D. Speedbreaker Codeforces Round 975 (Div. 2)

 原题

D. Speedbreaker

解析

这道题题意就是要找出来有多少个起点, 可以每次向左或者右扩展一个城市, 对每个城市在时间 t 到达 a[i] 前扩展到第 i 个城市

双指针来做, l 为左边界, r 为右边界, 只要有一个边界的值大于等于长度, 就缩短边界, 每次检查时更新可取的起点区域(ll, rr)

如果有可以成功的起点, 那么这种起点的数目就是 rr - ll + 1

代码 

#include <bits/stdc++.h>
#define int long longusing namespace std;const int N = 200010;int n, m, k, q, ans;int a[N];void solve()
{cin >> n;for (int i = 1; i <= n; i ++ ){cin >> a[i];}int l = 1, r = n, ll = 1, rr = n;int ans = 0;while (l <= r){int len = r - l + 1;//      起点要在a[l] - 1步内到达 l, 以下也是同理ll = max(ll, l - a[l] + 1);ll = max(ll, r - a[r] + 1);rr = min(rr, l + a[l] - 1);rr = min(rr, r + a[r] - 1);if (a[l] >= len && a[r] >= len){l ++ ;r -- ;}else if (a[l] >= len){l ++ ;}else if (a[r] >= len){r -- ;}else{cout << 0 << "\n";return;}}cout << max(0ll, rr - ll + 1) << "\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T = 1;cin >> T;while (T -- ){solve();}
}