posts - 99,  comments - 8,  trackbacks - 0
poj 1029
#include <stdio.h>
#include <stdlib.h>
#define MAX 1001
#define OK 1

int tag[MAX];  //将出现了等号的(即真币)排除    标记为1   遍历时跳过 
int num[MAX];  //记录下标为i的硬币在不等式的两边出现的次数 

int main ()
{
    
    int coin[MAX];   //访问时下标的中介 
    int N, k, pi, count ;
    char c;
    
    while ( scanf ("%d%d", &N, &k) != EOF )
    {
          count = 0;   //记录接下来的 k 次称量中有多少次出现了不等号 
          
          for ( int i = 0; i < k; i ++)  // k 次的称量记录 
          {
              scanf ("%d", &pi);
              for (int j = 0; j < 2 * pi; j ++)
              {
                  scanf ("%d", &coin[j]);
              }
              
              getchar ();
              
              c = getchar ();
              
              for (int i = 0; i < 2 * pi; i ++)
              {
                  if (c == '=')
                  tag[coin[i]] = 1;
                  
                  else if (c == '<')
                  {
                       count ++;
                       for (int j = 0; j < pi; j ++)
                       { 
                           num[coin[j]]--;
                       }
                       for (int j = pi; j < 2 * pi; j++)
                       {
                           num[coin[j]]++;
                       }
                  }
                  
                  else
                  {
                      count ++;
                       for (int j = 0; j < pi; j ++)
                       {
                           num[coin[j]]++;
                       }
                       for (int j = pi; j < 2 * pi; j++)
                       {
                           num[coin[j]]--;
                       }
                  }
              }
             
          }
          
          int mark = 0;
          int temp ;
          for (int i = 1; i <= N; i ++)
          {
              if (tag[i] == 1)  //表示为真币，不可能 
              continue;
              
              if (num[i] == count || num[i] == -count)   //如果硬币在不等式的两边出现的次数等于不等号数为假币 
              {
                         mark ++;
                         temp = i;
              }
          }
          
          if (mark == 1)    // 假币只有一个 
          {
             printf ("%d\n", temp);
          }
          
          else 
          printf ("%d\n",0);
            
    }
    
    return 0;
}
posted on 2010-08-29 11:49 雪黛依梦 阅读(408) 评论(0)  编辑 收藏 引用 所属分类: 蛮力

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2010年9月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜