hdu 4768 Flyer 长春市网络赛 1010 二分

hdu 4768 Flyer 长春网络赛 1010 二分

思路：因为只有一个是奇数，别的都是偶数，所以前面n个人收到的传单和为奇数时，表示解在1到n，那么就满足了单调性，可以二分解答。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=2e4+9;
const double inf=1e10;
int n;
struct D
{
    long long a,b,c;
}data[maxn];

long long cal(long long tmp)
{
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        long long mmin=min(tmp,data[i].b);
        if(mmin>=data[i].a)
        {
            ans+=(mmin-data[i].a)/data[i].c+1;
        }
    }
    return ans;
}

bool chk(long long tmp)
{
    long long ans=cal(tmp);
    return ans%2;
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%lld %lld %lld",&data[i].a,&data[i].b,&data[i].c);

        long long l=1,r=inf,mid;
        while(l<r)
        {
            mid=l+r>>1;
            if(chk(mid)) r=mid;
            else l=mid+1;
        }
        if(l==inf)
        printf("DC Qiang is unhappy.\n");
        else
        {
            printf("%d ",l);
            long long ans=cal(l)-cal(l-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}