Divide and conquer:Showstopper(POJ 3484)

　　　　　　　　　　　　　　　　Showstopper

　　题目大意：数据挖掘是一项很困难的事情，现在要你在一大堆数据中找出某个数重复奇数次的数（有且仅有一个），而且要你找出重复的次数。

　　其实我一开始是没读懂题意的。。。主要是我理解错object的意思了- -

　　这一题原理要做出来不难，其实就是二分法，对数二分就好了，因为重复奇数次的数只有一个，所以肯定存在小于等于某一个数时的数的重复次数加起来是奇数，不断二分就可

　　关键是是这一题的数据输入超级麻烦，他还会隔行输入。。。。用一行或者多行来区分数据。。。一开始我跳进这个坑里面了。。出题人有意思吗？

　　不过还好，让我重新复习了sscanf的用法。。。网上找了个用法比较好的做范例吧。

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 #include <string.h>
 5 
 6 typedef long long LL_INT;
 7 
 8 struct _set
 9 {
10     LL_INT set_att[3];
11 }refer[500005];
12 
13 void Solve(const int, LL_INT);
14 LL_INT Max(LL_INT, LL_INT);
15 bool judge(LL_INT, const int);
16 int Cal_Sum(const int, LL_INT);
17 
18 int main(void)//找出某个数出现的次数为奇数次的数
19 {
20     int sum = 0;
21     LL_INT max_num;
22     char str[100];
23 
24     while (gets(str))
25     {
26         sum = 0;  max_num = -1; refer[0].set_att[0] = 0;
27         sscanf(str, "%lld %lld %lld", &refer[0].set_att[0], &refer[0].set_att[1], &refer[0].set_att[2]);
28         if (refer[0].set_att[0] == 0)
29             continue;
30         memset(str, 0, sizeof(str));
31         do{
32             sum++;
33             gets(str);
34             if (str[0] == 0) break;
35             sscanf(str, "%lld %lld %lld", &refer[sum].set_att[0], &refer[sum].set_att[1], &refer[sum].set_att[2]);
36             memset(str, 0, sizeof(str));
37             max_num = Max(max_num, refer[sum].set_att[1]);
38         } while (1);
39         Solve(sum, max_num);
40     }
41     return EXIT_SUCCESS;
42 }
43 
44 LL_INT Max(LL_INT x, LL_INT y)
45 {
46     return x > y ? x : y;
47 }
48 
49 int Cal_Sum(const int i, LL_INT ans)
50 {
51     if (ans<refer[i].set_att[0] || ans>refer[i].set_att[1])
52         return 0;
53     else if ((ans - refer[i].set_att[0]) % refer[i].set_att[2] == 0)
54         return 1;
55     else return 0;
56 }
57 
58 void Solve(const int set_sum, LL_INT max_num)
59 {
60     LL_INT lb = 0, ub = max_num, mid, res = 0;
61 
62     while (ub - lb > 1)
63     {
64         mid = (lb + ub) >> 1;
65         if (judge(mid, set_sum)) ub = mid;
66         else lb = mid;
67     }
68     for (int i = 0; i < set_sum; i++)
69         res += Cal_Sum(i, ub);
70     if (res % 2)
71         printf("%lld %lld
", ub, res);
72     else
73         printf("no corruption
");
74 }
75 
76 bool judge(LL_INT mid, const int set_sum)
77 {
78     //只用统计mid(包含mid)的半边就可以了，因为出现奇数次的数只有一个
79     LL_INT refer_sum = 0;
80     for (int i = 0; i < set_sum; i++)
81     {
82         if (mid < refer[i].set_att[0])//没有任何数出现在左边
83             continue;
84         else if (mid > refer[i].set_att[1])
85             refer_sum += (refer[i].set_att[1]- refer[i].set_att[0]) / refer[i].set_att[2] + 1;
86         else
87             refer_sum += (mid - refer[i].set_att[0]) / refer[i].set_att[2] + 1;
88     }
89     return refer_sum % 2 ? 1 : 0;
90 }

　　参考http://blog.csdn.net/sd_invol/article/details/9410407

　　　　http://blog.csdn.net/u012825876/article/details/27854225