欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

防线-----------------------------------思维(前缀和+二分+套路题)

程序员文章站 2022-06-17 19:55:14
...

防线-----------------------------------思维(前缀和+二分+套路题)
防线-----------------------------------思维(前缀和+二分+套路题)

防线-----------------------------------思维(前缀和+二分+套路题)
解析:
1.根据题目所述,最多只有一个位置数量是奇数,那么说明所有位置上的数量之和也一定是奇数。
因为奇数+偶数=奇数
2.我们通过二分来确定位置。如果[l,mid]的数量总和是奇数那么就缩小范围,反之[mid+1,r]这部分肯定是偶数了。
3.数量总和可以用前缀和表示sum[x]:表示第x个位置之前所有位置上数量之和。
那么可以O(n)求解出总和。
假设s<=x 那么它们之间防具的数量=(min(e,x)-s)/d+1;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10000;
int t,n;
struct node
{
	int s,e,d;
}a[N];
ll check(int x)
{
	ll res=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].s<=x)  res+=(min(a[i].e,x)-a[i].s)/a[i].d+1;
	}
	return res;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int  l=0,r=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].s>>a[i].e>>a[i].d;
			r=max(r,a[i].e);
		 } 
		 int ans;
		 while(l<=r)
		 {
		 	int mid=l+r>>1;
		 	if(check(mid)&1) r=mid-1,ans=mid;
		 	else l=mid+1;
		 }
		 ll res=check(ans)-check(ans-1);
		 if(res&1) cout<<ans<<" "<<res<<endl;
		 else cout<<"There's no weakness."<<endl;
	}	
 }