[20170426 ADV] Samtopia Public Poll

// 20170426adv.cpp : Public Poll.
#include "stdafx.h"
#include <stdio.h>

int a[9];//保存一种组合
int b[9];//最初的组合
int sum0;
int sum1;
int sum2;
int weight[9];//保存权值
int map[3][9];
int conv[3][9];//统治一个town需要劝说的最少人数
int count=0;
int N;//town number
int convsum=-1;
int tmp;
void calc_conv_num(void)//遍历所有Town，计算该Town
{              //三个候选人分别获胜需要劝说的最小人数
   int j;
   for(j=0;j<N;j++)
   {
      if(map[0][j]>map[1][j] && map[0][j]>map[2][j])
      {
         conv[0][j]=0;

         conv[1][j]=(map[0][j]+2-map[1][j])/2;
         if((map[1][j]+conv[1][j]) < map[2][j])
            conv[1][j]=map[2][j]-map[1][j]+1;

         conv[2][j]=(map[0][j]+2-map[2][j])/2;
         if((map[2][j]+conv[2][j]) < map[1][j])
            conv[2][j]=map[1][j]-map[2][j]+1;

         b[j]=0;
      }
      else if(map[1][j]>map[0][j] && map[1][j]>map[2][j])
      {
         conv[0][j]=(map[1][j]+2-map[0][j])/2;
         if(map[0][j]+conv[0][j]<map[2][j])
            conv[0][j]=map[2][j]-map[0][j];

         conv[1][j]=0;

         conv[2][j]=(map[1][j]+2-map[2][j])/2;
         if(map[2][j]+conv[2][j] < map[0][j])
            conv[2][j]=map[0][j]-map[2][j]+1;

         b[j]=1;
      }
      else
      {
         conv[0][j]=(map[2][j]+2-map[0][j])/2;
         if(map[0][j]+conv[0][j] < map[1][j])
            conv[0][j]=map[1][j]-map[0][j]+1;

         conv[1][j]=(map[2][j]+2-map[1][j])/2;
         if(map[1][j]+conv[1][j] < map[0][j])
            conv[1][j]=map[0][j]-map[1][j]+1;

         conv[2][j]=0;
         b[j]=2;
      }
   }
}

void combination(int step)
{
   int i,j;
   if(step==N)
   {
      sum0=0;
      sum1=0;
      sum2=0;
      tmp=0;
      for(i=0;i<N;i++){//针对一种组合，分别计算每一个候选人的票数
         if(a[i]==0)
            sum0+=weight[i];
         else if(a[i]==1)
            sum1+=weight[i];
         else
            sum2+=weight[i];
      }
      if(sum2>sum0 && sum2>sum1)//当这种组合shark获胜
      {
         for(j=0;j<N;j++)
         {
            if(a[j]!=b[j])//如果和最初组合b不同，则需要劝说
            {
               tmp+=conv[a[j]][j];//累加需要劝说的人数
            }
         }
         if(convsum==-1)//第一次赋值
            convsum=tmp;
         else if(convsum>tmp)//tmp小于历史值，则更新历史值
            convsum=tmp;
      }
      return;
   }
   a[step]=0;//深度递归
   combination(step+1);
   a[step]=1;
   combination(step+1);
   a[step]=2;
   combination(step+1);
   return;
}

int _tmain(int argc, _TCHAR* argv[])
{
   int i,j;
   int t,test_case;
   freopen("20170426in.txt","r",stdin);
   scanf("%d",&test_case);
   for(t=1;t<=test_case;t++)
   {
      for(j=0;j<9;j++)
      {
         a[j]=-1;
         b[j]=-1;
         weight[j]=-1;
         for(i=0;i<3;i++)
         {
            map[i][j]=-1;
            conv[i][j]=-1;
         }
      }
      scanf("%d",&N);
      for(j=0;j<N;j++)
         scanf("%d",&weight[j]);
      for(i=0;i<3;i++)
         for(j=0;j<N;j++)
            scanf("%d",&map[i][j]);

      calc_conv_num();
      convsum=-1;
      combination(0);
      printf("#%d %d\n",t,convsum);
   }
   return 0;
}

/* in
5
7
55 80 5 35 80 70 80
65 60 75 80 50 50 80
60 80 70 95 95 95 45
25 50 35 45 10 15 35
5
75 20 35 10 40
90 95 90 50 40
95 70 95 45 55
35 60 20 35 10
9
30 65 25 40 85 45 75 45 60
80 70 15 70 20 40 45 55 55
40 85 95 40 95 35 65 65 60
30 40 10 20 15 15 10 50 20
7
29 5 5 30 15 5 34
50 60 95 90 35 75 85
55 90 45 80 30 95 15
40 10 15 10 25 35 10
9
381 524 194 944 172 406 204 970 525
333 643 366 800 717 281 647 739 332
804 953 579 972 493 693 680 969 747
71 537 169 248 63 181 380 437 315
*/

/* out
#1 47
#2 59
#3 73
#4 23
#5 746
*/