xindoo is
always here

hdoj 4768 Flyer

题目意思很容易理解,学校有n个社团,每个社团只给编号从a到b 的发传单,而且只给隔了c的人发,问最后谁收到的传单是单数,输出他的编号和收到的传单数量。

昨天做这题的时候看见很多人过了,感觉不会很难,但是打死都想不出来,看了别人的思路,一下子就想通了。这里我简要说一下,用二分,我们可以很容易求出一段区间里的总的传单数,因为保证最多有一个是单数,我们就看单数在哪边。

下面是java代码,刚开始学java,代码不是很简洁。

import java.util.Scanner;

public class Main {
    static long[] a = new long[20005];
    static long[] b = new long[20005];
    static long[] c = new long[20005];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            int n = cin.nextInt();
            for (int i = 1; i <= n; i++) {
                a[i] = cin.nextLong();
                b[i] = cin.nextLong();
                c[i] = cin.nextLong();
            }
            long r = Integer.MAX_VALUE, l = 0;
            while (l < r) {
                long mid = (l+r)>>1;
                long sum = 0;
                for (int i = 1; i <= n; i++) {
                    long minnum;
                    if (mid <= b[i])
                        minnum = mid;
                    else 
                        minnum = b[i];
                    if (minnum >= a[i]) {
                        sum += (minnum - a[i])/c[i] + 1;
                    }
                }
                if (sum%2 == 1)
                    r = mid;
                else l = mid+1;
            }
            if (l == Integer.MAX_VALUE) {
                System.out.println("DC Qiang is unhappy.");
                continue;
            }
            long ans = 0;
            for (int i = 1; i <= n; i++) {
                if (l >= a[i] && l <= b[i]) {
                    if ((l - a[i]) % c[i] == 0)
                        ans += 1;
                }
            }
            System.out.println(l + " " + ans);
        }
        cin.close();
    }
}

打赏
未经允许不得转载:XINDOO » hdoj 4768 Flyer
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏