POJ1029 & POJ1013 - 找哪个是假硬币...思维

这道题就是说有N个硬币....其中有一个硬币是假币(不知道是比真币重还是轻)....然后给出K个大小关系....要我们来判断哪个是假币或者判断不出输出0....

我的主要思想就是....有不等关系...肯定两边就有假币存在...那么假币出现的个数就一定等于不等关系的个数....然后稍微整理和完善一下...

首先...如果有称出是相等的...那么两边的硬币肯定都是真币 ( 两边硬币一样多...N个里只有一个是假币...所以平衡了两边肯定都是真币)....把这些硬币都标记一下...后面的处理可以忽略这些硬币了....

然后把每次不等的情况先记录下来.为了方便处理...将 > 的情况前后两半对调一下再存...这样存的不等情况都是左边的一半小于右边的一半..准备两个数组..我是用left记录轻了的一边每个硬币出现的个数...right记录重的一边出现的个数...扫描所有的不等情况...将左半边的数 left [ i ] ++...右半边的数 right [ i ] ++ .... 做完以后分别扫描左右两边...找到出现次数等于不等关系个数的硬币...在这里还要多几个判断...如果有两个满足条件..那就无法判断...return 0....如果当前硬币满足条件...但在前面做平衡情况的时候已经标记了...这个硬币也肯定不能是真币...

写的时候细心点就可以过了吧~~~

Program:

#include<iostream>
#define MAXN 1001
using namespace std;
struct pp
{
    int w,s[MAXN];   
}h[101],temp;
int N,K,m,x,i;
bool f[MAXN]; 
char c;
int GetAnswer()
{
     int ans=0,i,type,k,left[MAXN],right[MAXN];
     memset(left,0,sizeof(left));
     memset(right,0,sizeof(right));
     for (k=1;k<=m;k++)
     {
         for (i=1;i<=h[k].w/2;i++) left[h[k].s[i]]++;
         for (i=h[k].w/2+1;i<=h[k].w;i++) right[h[k].s[i]]++;
     }
     for (i=1;i<=N;i++)
      if (left[i]==m && !f[i])
       {
          if (!ans) ans=i;
          else return 0;              
       }
     for (i=1;i<=N;i++)
      if (right[i]==m && !f[i])
       {
          if (!ans || ans==i) ans=i;
          else return 0;              
       }
     return ans;
}
int main()
{
     scanf("%d%d",&N,&K);
     memset(f,false,sizeof(f));
     m=0;
     while (K--)
     {
         scanf("%d",&temp.w);
         temp.w=temp.w*2;
         for (i=1;i<=temp.w;i++) scanf("%d",&temp.s[i]);
         getchar(); c=getchar();
         if (c=='=')
         {
            for (i=1;i<=temp.w;i++)
              f[temp.s[i]]=true;        
         }else
         {
            m++;
            h[m]=temp;
            if (c=='>')
            {
                for (i=1;i<=temp.w/2;i++) h[m].s[i+temp.w/2]=temp.s[i];
                for (i=temp.w/2+1;i<=temp.w;i++) h[m].s[i-temp.w/2]=temp.s[i];  
            } 
         }           
     }
     printf("%d\n",GetAnswer());
     return 0;   
}

PS...POJ1013也是类似的题..比1029还简单一些....稍微改一下就可以过了~~