AcWing 120. 防线
原题链接
中等
作者:
开心小子
,
2019-09-19 15:00:51
,
所有人可见
,
阅读 755
#include<iostream>
#include<algorithm>
using namespace std;
//本题有一个很好的特点是只有一点为奇数个士兵,那么也表示改点之后的所有点的前缀和的和为奇数
//那么我们就可以利用这个性质,利用前缀和的方式下在利用二分优化,以顺利完成题目
const int maxn=200020;
#define ll long long
//考虑s、e、q的范围在计算是很可能会超出整数范围,这里使用long long 类型定义变量
struct Seq{
ll s,e,q;
}seq[maxn];
int t,n;
ll check(ll x)
{
//计算某一点的前缀和,这里利用等差数列的性质求前缀和
ll res=0;
for(int i=0;i<n;i++)
if(seq[i].s<=x)
{
ll s=min(x,seq[i].e)-seq[i].s;
res+=s/seq[i].q+1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
ll l=0,r=0;//确定二分的范围
cin>>n;
for(int i=0;i<n;i++)
{
ll s,e,q;
cin>>s>>e>>q;
seq[i]={s,e,q};
r=max(r,e);
}
while(l<r)
{
ll mid=(l+r)>>1;
if(check(mid)&1)//当前缀和为奇数是符合题意
r=mid;
else l=mid+1;
}
ll sum=check(r)-check(r-1);
if(sum%2==0)puts("There's no weakness.");
else cout<<r<<" "<<sum<<endl;
}
return 0;
}