防线-----------------------------------思维(前缀和+二分+套路题)
程序员文章站
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;
}
}