【BeijingWc 2008】 秦腾与教学评估

【题目链接】

           https://www.lydsy.com/JudgeOnline/problem.php?id=1271

【算法】

           二分

【代码】

           

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200100

int T,i,n,ans;
long long l,r,mid;
long long s[MAXN],d[MAXN],e[MAXN];

inline long long calc(long long x)
{
        int i;
        long long ret = 0;
        for (i = 1; i <= n; i++)    
        {
                if (s[i] <= x) 
                        ret += (min(e[i],x) - s[i]) / d[i] + 1;        
        }    
        return ret;
}

int main() 
{
        
        scanf("%d",&T);
        while (T--)
        {
                ans = 0;
                scanf("%d",&n);
                for (i = 1; i <= n; i++) scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
                l = 1; r = 2147483647;
                if (calc(r) % 2 == 0) 
                {
                        printf("Poor QIN Teng:(
");
                        continue;
                }
                while (l <= r)
                {
                        mid = (l + r) >> 1;
                        if (calc(mid) & 1) 
                        {
                                ans = mid;
                                r = mid - 1;
                        } else l = mid + 1;
                }
                if (ans) printf("%d %lld
",ans,calc(ans)-calc(ans-1));
        }
        return 0;
    
}