首页 > 其他分享 >B. Speedbreaker

B. Speedbreaker

时间:2024-10-18 19:22:54浏览次数:3  
标签:cout int long pa sec include Speedbreaker

链接:https://codeforces.com/problemset/problem/2018/B
题目:

思路:
刚开始的思路是对的,就是每个点确定范围求交集。然后还要判断一下会不会无解,比如[5,6,4,1,4,5],就是说∃t∈[1,n],st:a[x]<=n,a[y]<=n,max(x)-min(y)>=t时无解,因为两侧如果更大、更小就会冲突。
代码:

#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = 2e5 + 10;

int a[N];
struct pa
{
	int first, sec;
	pa(int f, int s) { first = f; sec = s; }
	pa(){}
};
bool cmp_s(pa a, pa b) { return a.sec < b.sec; }
void solve()
{
	int n; cin >> n;
	for (int i = 1; i <= n; i++) { int x; cin >> x; a[i] = x; }
	int l =0 , r = LLONG_MAX;
	for (int i = 1; i <= n; i++)
	{
		int lnow = max((int)1, i - a[i] + 1);
		int rnow = min(n, i + a[i] - 1);
		l = max(l, lnow), r = min(r, rnow);
	}
	vector<pa>vt;
	for (int i = 1; i <= n; i++)vt.push_back(pa(i, a[i]));
	sort(vt.begin(), vt.end(), cmp_s);
	int maxn = 0, minn = LLONG_MAX;
	int cnt = 1;
	bool jmp = false;
	for (pa x : vt)
	{
		if (jmp)break;
		minn = min(minn, x.first);
		maxn = max(maxn, x.first);
		cnt = x.sec;//这里直接修改cnt=x.sec就可以
		if (maxn - minn >= cnt)jmp = true;
		
	}
	if (jmp)cout << 0;
	else cout << r - l + 1;
	cout << '\n';


}


signed main()
{
	IOS;
	int t; cin >> t;
	while (t--)
		solve();
	return 0;
}

标签:cout,int,long,pa,sec,include,Speedbreaker
From: https://www.cnblogs.com/zzzsacmblog/p/18474909

相关文章

  • CF2019D Speedbreaker
    题意Link一个数轴上有\(1,2,\dots,n\)共\(n\)个点。第\(1\)秒时,你将从其中一个点开始染色,称为初始点,之后第\(2,3,\dots,n\)秒,你每秒可以将一个被染色的点左边或右边的点染色。每个点有一个时间限制,必须要在\(a_i\)秒前(包含第\(a_i\)秒)被染色,问有多少个初始点可以将......
  • CF2019D. Speedbreaker 题解
    介绍一种另解,以下称“征服”为“拓展”。对于这些需要拓展,且拓展的时间有上界的题,我们通常都会有一个trick。那就是对于一个点\(x\),用它可以拓展到的点\(y\)的时间上界把\(x\)的时间上界继续缩小。用到这种trick的题有P9755[CSP-S2023]种树、[ABC304Ex]ConstrainedTop......