【数据结构】USACO clocks

前端之家收集整理的这篇文章主要介绍了【数据结构】USACO clocks前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

最暴力的办法,开始超了。改了一些循环的控制就对了。

http://acm.sjtu.edu.cn/OnlineJudge/problem/1047


#include <iostream>
//clock
//usaco
#include <fstream>
using namespace std;
void change(int &x)
{
    x=(x+3)%12;
}
void change(int n,int a[])
{
    if(n==0) {change(a[0]);change(a[1]);change(a[3]);change(a[4]);}
    if(n==1) {change(a[0]);change(a[1]);change(a[2]);}
    if(n==2) {change(a[1]);change(a[2]);change(a[4]);change(a[5]);}
    if(n==3) {change(a[0]);change(a[3]);change(a[6]);}
    if(n==4) {change(a[1]);change(a[3]);change(a[4]);change(a[5]);change(a[7]);}
    if(n==5) {change(a[2]);change(a[5]);change(a[8]);}
    if(n==6) {change(a[3]);change(a[4]);change(a[6]);change(a[7]);}
    if(n==7) {change(a[6]);change(a[7]);change(a[8]);}
    if(n==8) {change(a[4]);change(a[5]);change(a[7]);change(a[8]);}
}
void change(int n,int times,int a[])
{
    if(n==0) for(int i=0;i<times;++i){change(a[0]);change(a[1]);change(a[3]);change(a[4]);return;}
    if(n==1) for(int i=0;i<times;++i){change(a[0]);change(a[1]);change(a[2]);return;}
    if(n==2) for(int i=0;i<times;++i){change(a[1]);change(a[2]);change(a[4]);change(a[5]);return;}
    if(n==3) for(int i=0;i<times;++i){change(a[0]);change(a[3]);change(a[6]);return;}
    if(n==4) for(int i=0;i<times;++i){change(a[1]);change(a[3]);change(a[4]);change(a[5]);change(a[7]);return;}
    if(n==5) for(int i=0;i<times;++i){change(a[2]);change(a[5]);change(a[8]);return;}
    if(n==6) for(int i=0;i<times;++i){change(a[3]);change(a[4]);change(a[6]);change(a[7]);return;}
    if(n==7) for(int i=0;i<times;++i){change(a[6]);change(a[7]);change(a[8]);return;}
    if(n==8) for(int i=0;i<times;++i){change(a[4]);change(a[5]);change(a[7]);change(a[8]);return;}
   // for(int i=0;i<times;++i)
   //     change(n,a);
}
bool judge(int a[])
{
    for(int i=0;i<9;++i)
        if(a[i]!=0)
            return false;
    return true;
}
int sum(int a[])
{
    int s=0;
    for(int i=0;i<9;++i)
        s+=a[i];
    return s;
}
bool lessOrder(int s[],int r[])
{
    for(int i =0;i<9;++i)
    {
        if(s[i]>r[i])
            return true;
    }
    return false;
}
int main()
{
    //freopen("clocks.in","r",stdin);
    //freopen("clocks.out","w",stdout);
    //如果是在usaco可以把上面两句去掉
    int a[9];
    for(int i=0;i<9;++i){cin>>a[i];a[i]=a[i]%12;}
    int st[9];
    int min=36;
    int result[9];
    int clocks[9];
    for(st[0]=0;st[0]<=3;++st[0])
    {
        for(st[1]=0;st[1]<=3;++st[1])
            for(st[2]=0;st[2]<=3;++st[2])
            for(st[3]=0;st[3]<=3;++st[3])
            for(st[4]=0;st[4]<=3;++st[4])
            for(st[5]=0;st[5]<=3;++st[5])
            for(st[6]=0;st[6]<=3;++st[6])
            for(st[7]=0;st[7]<=3;++st[7])
            for(st[8]=0;st[8]<=3;++st[8])
            {
                if(sum(st)>min) continue;
                for(int i=0;i<9;++i)
                    clocks[i]=a[i];
                for(int j=0;j<9;++j)
                    for(int k=0;k<st[j];++k)
                        change(j,st[j],clocks);
                if(judge(clocks)){
                    //if(sum(st)<=min)
                   // {
                        if(sum(st)<min)
                        {
                            min = sum(st);
                            for(int i=0;i<9;++i)
                                result[i]=st[i];
                        }
                        else{
                            if(lessOrder(st,result))
                                for(int i=0;i<9;++i)
                                    result[i]=st[i];
                        }
                   // }
                }
            }
    }
    for(int i=0;i<9;++i)
    {
        if(result[i]!=0)
        {
            for(int j=0;j<result[i];++j)
                cout<<i+1<<' ';
        }
    }
    return 0;
}



猜你在找的数据结构相关文章