首页 > 专题系列 > Java解POJ > POJ 3657 Haybale Guessing [解题报告] Java
2013
11-13

POJ 3657 Haybale Guessing [解题报告] Java

Haybale Guessing

问题描述 :

The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.

A designated ‘Hay Cow’ hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.

The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:

What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ≤ QlN; QlQhN)?

The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.

Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.

输入:

* Line 1: Two space-separated integers: N and Q
* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A

输出:

* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.

样例输入:

20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出:

3

解题代码:

//* @author 
/*题目问题可以转化为判断questions是否矛盾, 然后二分找到最先发生矛盾的question.
 *那如何判断矛盾? 若我们把questions依照Ai值从大到小的顺序进行区间覆盖, 若一个区间加入时,
 * 此区间已被完全覆盖, 则说明此区间的取 

*值均比Ai大, 故questions矛盾, 否则一定可以构造出一个取值分布. 
 *区间覆盖最好的方法应该是线段树, 然而此题只需要判断某段区间是否被覆盖, 所以可以用并查集维护. 
 *复杂度O(aQlogQ)(a为并查集系数)
  */
/**
 * @version 2009/08/22
 * @author sbzlyessit
 */

import java.io.*;
import java.util.*;

public class Main {

    private static final int        MAX_N = 25000;

    private static BufferedReader   in =
            new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer  st;
    private static int[][]          que = new int[MAX_N][3];
    private static int[]            x = new int[2 * MAX_N];
    private static Integer[]        list = new Integer[MAX_N];
    private static int[]            r = new int[2 * MAX_N];
    private static boolean[]        used = new boolean[2 * MAX_N];
    private static int              N, xSize;

    public static void main(String[] argv) throws Exception {
        readIn();
        solve();
    }

    private static void readIn() throws Exception {
        int i, temp;
        nextInt();
        N = nextInt();
        for (xSize = 0, i = 0; i < N; i++) {
            que[i][0] = x[xSize++] = nextInt();
            que[i][1] = x[xSize++] = nextInt() + 1;
            que[i][2] = nextInt();
            list[i] = i;
        }
        Arrays.sort(x, 0, xSize);
        for (temp = xSize, xSize = i = 1; i < temp; i++) {
            if (x[i] != x[i - 1]) {
                x[xSize++] = x[i];
            }
        }
        for (i = 0; i < N; i++) {
            que[i][0] = Arrays.binarySearch(x, 0, xSize, que[i][0]);
            que[i][1] = Arrays.binarySearch(x, 0, xSize, que[i][1]);
        }
        Arrays.sort(list, 0, N, new Comparator(){
            public int compare(Integer a, Integer b) {
                return que[a][2] < que[b][2] ? 1 : -1;
            }
        });
    }

    private static void solve() {
        int min = 0, max = N - 1, mid;
        while (min < max) {
            mid = (min + max + 1) / 2;
            if (check(mid)) {
                min = mid;
            } else {
                max = mid - 1;
            }
        }
        if (min == N - 1) {
            System.out.println(0);
        } else {
            System.out.println(min + 2);
        }
    }

    private static boolean check(int pos) {
        int     i, j, x, min, max;
        boolean found;
        for (i = 0; i < xSize - 1; i++) {
            r[i] = -1;
            used[i] = false;
        }
        for (i = 0; i < N; i++) {
            x = list[i];
            if (i == 0 || que[x][2] != que[list[i - 1]][2]) {
                min = Integer.MIN_VALUE;
                max = Integer.MAX_VALUE;
                for (j = i; j < N && que[list[j]][2] == que[x][2]; j++) {
                    if (list[j] <= pos) {
                        min = Math.max(min, que[list[j]][0]);
                        max = Math.min(max, que[list[j]][1]);
                    }
                }
                if (min != Integer.MIN_VALUE) {
                    for (found = false, j = min; j < max; j++) {
                        if (!used[j]) {
                            used[j] = found = true;
                            insert(j);
                        }
                        j = find(j);
                    }
                    if (!found) {
                        return false;
                    }
                }
            }
            if (x <= pos) {
                for (j = que[x][0]; j < que[x][1]; j++) {
                    if (!used[j]) {
                        used[j] = true;
                        insert(j);
                    }
                    j = find(j);
                }
            }
        }
        return true;
    }

    private static void insert(int pos) {
        if (pos > 0 && used[pos - 1]) {
            r[pos - 1] = pos;
        }
        if (pos < xSize - 2 && used[pos + 1]) {
            r[pos] = find(pos + 1);
        }
    }

    private static int find(int x) {
        int y = x, z;
        while (r[y] != -1) {
            y = r[y];
        }
        while (x != y) {
            z = x;
            x = r[x];
            r[z] = y;
        }
        return y;
    }

    private static int nextInt() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }

}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  3. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?