百度之星-ARM-STM32竞赛算法题求解

小菜儿

糖果

Description

度度熊最近一直在陪小朋友玩，有一天，他放到桌子上的糖不见了，而屋里一共有N个小朋友，于是度度熊想知道是谁拿走了糖果，于是他就去问N个小朋友。

每个小朋友都会告诉他一句话。这句话的形式为糖果是A拿的，或者是糖果不是A拿的。

不幸的是一些小朋友会说谎，度度熊知道恰好有K个小朋友说谎，现在他想请你帮帮忙，帮他算出是谁拿走了糖果。

Input Format

第一行为数据组数T(1≤T≤100)。

每组数据第一行为整数N(1≤N≤10000)和K(1≤K≤N)表示小朋友的个数和说谎的小朋友的个数。之后K行每行由两个数字a, b组成，a = 1表示该小朋友告诉度度熊是b拿走了糖果，a = 0表示该小朋友告诉度度熊不是b拿走了糖果。小朋友的编号从1开始。

Output Format

每组数据输出一个整数，为拿走糖果的小朋友的编号

如果没有符合条件的小朋友，就输出"0"

如果有不止一个小朋友符合条件，那么就输出"-1"

Sample Input

2

4 1

1 2

1 3

1 2

1 2

4 0

1 2

1 1

1 2

1 2

Sample Output

2

0

小菜儿

参赛者宁伟给出的一种解答，大家可以讨论下！

1. #include <cstdio>
   
2. #include <iostream>
   
3. using namespace std;
   
4. #define abs(x) ((x)>=0?(x):(-x))
   
5. int x[10004];
   
6. int main()
   
7. {
   
8. int t, n, k, b, xb, temp, r, s;
   
9. cin >> t;
   
10. while (t--)
    
11. {
    
12. r = s = 0;
    
13. cin >> n >> k;
    
14. for (int i = 1; i <= n; ++i)
    
15. {
    
16. scanf("%d%d", &b, &xb);
    
17. temp = x[xb];
    
18. if (b)
    
19. ++x[xb];
    
20. else
    
21. --x[xb];
    
22. if (abs(temp) > abs(x[xb]))
    
23. --k;
    
24. }
    
25. for (int i = 1; i <= n; ++i)
    
26. s += x[i] > 0 ? x[i] : 0;
    
27. for (int i = 1; i <= n; ++i)
    
28. if (n - x[i] == k)
    
29. if (r)
    
30. {
    
31. r = -1;
    
32. break;
    
33. }
    
34. else
    
35. r = i;
    
36. if (k < 0)
    
37. r = 0;
    
38. cout << r << endl;
    
39. }
    
40. return 0;
    
41. }

复制代码

小菜儿

百度网友“杨建明_yjm”的解答：

解题思路：
把说谎话的人数转成说实话的人数，然后对比每个小朋友被别人说偷了的人数。说某人没偷的情况也转成说其他人偷了。程序使用了随机数据，不用手动输入了。有问题的话请指出。另外谁有其他正确的测试数据？请贴出来。
本人代码：
//请保存成sweet.java
//作者：杨建明
import java.util.*;
class sweet {
int [] who;//说谁
boolean [] state;//是否拿了
int [] total_people;//如果是这人拿的，有多少人说的是实话
int N;//总人数
int k;//说谎人数
int M;//说实话人数
HashMap<Integer ,Integer> total_person_Map;//统计总共有多少人说某某人。hashmap效果不好，改为total_people数组
Iterator it;
int result;//结果
int who_number;//符合条件的小朋友的编号

//声明一个数据输入的函数
public void scannerInput()
{
  Scanner scan = new Scanner(System.in);
      System.out.print("请输入测试数据的总组数：");
  int T = scan.nextInt();
  scan.nextLine();//光标移动到下一行开始
  for(int loop=1;loop<=T;loop++)
  {//loop循环开始
      System.out.println(" ");
      System.out.print("请输入N, K：");
    N = scan.nextInt();
    k = scan.nextInt();
    M = N - k; //说实话的人数
    total_person_Map = new HashMap<Integer,Integer>();
    result = 0;
    who_number = 0;

    scan.nextLine(); //读取一行 ，其实是把光标转到下一行开头，从头读取
    state  = new boolean[N + 1];//说某人偷了还是没偷
    who = new int[N + 1];//说谁
    total_people = new int[N + 1];//如果是这人拿的，有多少人说的是实话
/*************************
    for(int i=1;i<=N;i++)
    {
      System.out.print("第" + i + "个小朋友数据：");
       state[ i ] = scan.nextInt() == 0 ? false : true;
       who[ i ] = scan.nextInt();
       scan.nextLine(); //读取一行 ，其实是把光标转到下一行开头，从头读取
    }
************************/
    Random rnd = new Random();
    for(int i=1;i<=N;i++)
    {
       state[ i ] = rnd.nextInt(2) == 0 ? false : true;
       who[ i ] = rnd.nextInt(N) + 1;
    }

    //调用处理函数
    process_handling();
  }//loop循环结束
}



public void process_handling()
{//函数开始
   //循环所有人，统计某某人有多少人说他偷了

   for(int i=1;i<=N;i++)
   {
      if(state[ i ] != false)
      {
/*********************
        int temp = 0;
        if(total_person_Map.get(who[ i ]) != null)
        {
          temp = (Integer)total_person_Map.get(who[ i ]);
          temp += 1;
          total_person_Map.put(who[ i ] , temp);
        }
        else
        {
          total_person_Map.put(who[ i ] , 1);
        }
********************/
        total_people[who[ i ]] += 1;
      }
   }

  //还要把那些说某人没偷的加上
   for(int i=1;i<=N;i++)
   {
      if(state[ i ] == false)
      {

          //除了他说没偷的那个人，其他人都加1
          for(int j=1;j<=N;j++)
          {
            if(who[ i ] != j)
            {
/********************
             int temp = 0;
             if(total_person_Map.get(j) != null)
             {
                 temp = (Integer)total_person_Map.get(j);
                 temp += 1;
                 total_person_Map.put(j , temp);
             }
             else
             {
                 total_person_Map.put(j , 1);
             }
********************/
             total_people[j] += 1;
            }
          }

      }
   }

/*************************
  //循环map统计结果
  it = total_person_Map.entrySet().iterator();
  while (it.hasNext())
  {
    Map.Entry entry = (Map.Entry) it.next();
    Object key = entry.getKey();
    Object value = entry.getValue();
    int total_p = (Integer)value;
    if(total_p == M)
    {
       who_number = (Integer)key;
       result += 1;//总共有几个孩子符合条件
    }
  }
*************************/
   //统计结果
   for(int i=1;i<=N;i++)
   {
    if(total_people[ i ] == M)
    {
       who_number = i;
       result += 1;//总共有几个孩子符合条件
    }
   }

   System.out.println("*************************");
   System.out.println("随机原始数据：");
   if(N <30)
   {
     for(int i=1;i<=N;i++)
     {
       System.out.println(state[ i ] + " " + who[ i ]);
     }
   }
   else
   {
       System.out.println("多于30个，不显示了，因为太多。");
   }

   System.out.println("结论：");
   System.out.println("总共" + result + "个小朋友符合条件");
   if(result == 1)
   {
      System.out.println("第" + who_number + "个小朋友");
   }
}//函数结束




public static void main(String[] args) {
sweet s = new sweet(); //构造一个类的实例
s.scannerInput();

//System.out.println("恭喜你成功运行了第一个java应用程序!");
}
}

1.谁有其他正确的测试数据？请贴出来
  

谁有其他正确的测试数据？请贴出来

2.如果是全否定

3.用随机数模拟输入数据


自己生成随机数模拟数据
sweet.rar (1.62 KB, 下载次数: 0)

2013-6-17 10:07 上传

点击文件名下载附件
自己生成随机数模拟数据

xiaopaohu123

电脑程序破案的例证……

l廖天一阁主

这C++写的。。我表示我们学电的这个不行啊！！！

Hayasaky

我看到题目表示一个都不会……亚历山大

Xy201207

C语言写的用VC++6.0编译的，BUG不少欢迎参考