百度之星-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

4 0

1 2

1 1

1 2

Sample Output

2

0

小菜儿 · 发表于 2013-6-17 09:50:58

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

#include <cstdio>
#include <iostream>
using namespace std;
#define abs(x) ((x)>=0?(x):(-x))
int x[10004];
int main()
{
int t, n, k, b, xb, temp, r, s;
cin >> t;
while (t--)
{
r = s = 0;
cin >> n >> k;
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &b, &xb);
temp = x[xb];
if (b)
++x[xb];
else
--x[xb];
if (abs(temp) > abs(x[xb]))
--k;
}
for (int i = 1; i <= n; ++i)
s += x[i] > 0 ? x[i] : 0;
for (int i = 1; i <= n; ++i)
if (n - x[i] == k)
if (r)
{
r = -1;
break;
}
else
r = i;
if (k < 0)
r = 0;
cout << r << endl;
}
return 0;
}

复制代码

小菜儿 · 发表于 2013-6-17 10:08:57

本帖最后由 xinxincaijq 于 2013-6-17 10:11 编辑

百度网友“杨建明_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.谁有其他正确的测试数据？请贴出来