POJ 3139 Balancing the Scale-白红宇

POJ 3139 Balancing the Scale

阅读量：7082 次

发布时间：2019-06-28

本文共 1240 字，大约阅读时间需要 4 分钟。

枚举。

看了这个方法：$http://www.cppblog.com/shiming413/archive/2008/12/21/29671.html$

将数字归类的地方不能用$vector$，会超时。$vector$换成数组就可以过，类似于邻接表。

因为题目给出的$16$个数字都是不同的，所以时间复杂度相对还比较低。

下面这组数据是极限数据，我的跑了$3800$$ms$。但测试数据中不会出现这样的数据。

$5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$ $5$

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template 
               
                inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}int a[20],b[20];LL h[(1<<16)+10];struct X{ int b, nx;}e[50000];int g[11000],k;void add(int a,int b){ e[k].b=b; e[k].nx=g[a]; g[a]=k++;}int main(){ int cas=1; while(~scanf("%d",&a[0])) { if(a[0]==0) break; for(int i=1;i<=15;i++) scanf("%d",&a[i]); k=0; memset(g,-1,sizeof g); for(int i=0;i<(1<<16);i++) { int t=i,cnt=0; for(int j=0;j<16;j++) if(i&(1<