hdu 4768 Flyer 思路+二分

时间:2021-08-09 00:22:03


n个最多2W个社团发传单,因为传单不够,所有只能按照学生学号间隔着发……  比如发给A_i,A-i+k,A_i+2*k  ,只要不大于B_I就好;

而且已知收到传单的同学当中只有一个人收到奇数张;

这个题初看没有思路,但是仔细一想就挺简单了,在某个学号范围内比如说1-x范围内,根据社团发传单的数量,我们很容易知道他是按照等差数列来发送的,所以可能很容易算出这段区间内有多少张发出去,统计完所有的社团然后只要是奇数,那么那个唯一的收获奇数张的同学就在里面,然后利用二分的思想把这一段区间精确到1……


http://acm.hdu.edu.cn/showproblem.php?pid=4768


下面的代码是借用山科的

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=20010;
long long A[maxn],B[maxn],C[maxn];
long long cal(long long mid,int n){
    long long sum=0;
    for (int i=0;i<n;i++){
        long long up=min(mid,B[i]);
        if (up>=A[i])
        sum+=(up-A[i])/C[i]+1;
    }
//    cout<<mid<<" "<<sum<<endl;
    return sum;
}
int main()
{
    int n;
    while (scanf("%d",&n)==1)
    {
        for (int i=0;i<n;i++){
            cin>>A[i]>>B[i]>>C[i];
        }
        long long L=0,R=1LL<<31;
        while (L<R){
            long long mid=(L+R)/2;
            if (cal(mid,n)%2) R=mid;
            else L=mid+1;
        }
        if (L==1LL<<31)
            cout<<"DC Qiang is unhappy."<<endl;
        else {
            while (cal(L,n)%2==0) L--;
            cout<<L<<' '<<cal(L,n)-cal(L-1,n)<<endl;
        }
    }
    return 0;
}