Divide and conquer:Showstopper(POJ 3484)

　　　　　　　　　　　　　　　　Showstopper

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

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

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

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

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

 #include <iostream>

 #include <functional>

 #include <algorithm>

 #include <string.h>

 typedef long long LL_INT;

 struct _set

 {

     LL_INT set_att[];

 }refer[];

 void Solve(const int, LL_INT);

 LL_INT Max(LL_INT, LL_INT);

 bool judge(LL_INT, const int);

 int Cal_Sum(const int, LL_INT);

 int main(void)//找出某个数出现的次数为奇数次的数

 {

     int sum = ;

     LL_INT max_num;

     char str[];

     while (gets(str))

     {

         sum = ;  max_num = -; refer[].set_att[] = ;

         sscanf(str, "%lld %lld %lld", &refer[].set_att[], &refer[].set_att[], &refer[].set_att[]);

         if (refer[].set_att[] == )

             continue;

         memset(str, , sizeof(str));

         do{

             sum++;

             gets(str);

             if (str[] == ) break;

             sscanf(str, "%lld %lld %lld", &refer[sum].set_att[], &refer[sum].set_att[], &refer[sum].set_att[]);

             memset(str, , sizeof(str));

             max_num = Max(max_num, refer[sum].set_att[]);

         } while ();

         Solve(sum, max_num);

     }

     return EXIT_SUCCESS;

 }

 LL_INT Max(LL_INT x, LL_INT y)

 {

     return x > y ? x : y;

 }

 int Cal_Sum(const int i, LL_INT ans)

 {

     if (ans<refer[i].set_att[] || ans>refer[i].set_att[])

         return ;

     else if ((ans - refer[i].set_att[]) % refer[i].set_att[] == )

         return ;

     else return ;

 }

 void Solve(const int set_sum, LL_INT max_num)

 {

     LL_INT lb = , ub = max_num, mid, res = ;

     while (ub - lb > )

     {

         mid = (lb + ub) >> ;

         if (judge(mid, set_sum)) ub = mid;

         else lb = mid;

     }

     for (int i = ; i < set_sum; i++)

         res += Cal_Sum(i, ub);

     if (res % )

         printf("%lld %lld\n", ub, res);

     else

         printf("no corruption\n");

 }

 bool judge(LL_INT mid, const int set_sum)

 {

     //只用统计mid(包含mid)的半边就可以了，因为出现奇数次的数只有一个

     LL_INT refer_sum = ;

     for (int i = ; i < set_sum; i++)

     {

         if (mid < refer[i].set_att[])//没有任何数出现在左边

             continue;

         else if (mid > refer[i].set_att[])

             refer_sum += (refer[i].set_att[]- refer[i].set_att[]) / refer[i].set_att[] + ;

         else

             refer_sum += (mid - refer[i].set_att[]) / refer[i].set_att[] + ;

     }

     return refer_sum %  ?  : ;

 }

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

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

巴特西

Divide and conquer:Showstopper(POJ 3484)

最新文章

热门文章