题意

https://vjudge.net/problem/CodeForces-1255D

rxc的农场里'R'表示有米，现在有K只鸡，给这k只鸡选一些格子，每个鸡可以有多个格子（每个鸡至少吃一个米），但是每个鸡的格子必须连通。问吃到最多的米和最少的米的差最小是多少。

思路

如果农场一共有cnt个米，那么最优的分配肯定是差值为1或0，即给每个鸡先分cnt/k个米，然后把多余的分配给每个鸡。因为鸡的格子必须是连通的，所以可以考虑类似蛇形填数的方法，每找到cnt/k（多余的类似）个米就换下一只鸡，这样就能保证是连通而且差值最小了。

代码写的有点冗长，我的判断退出的方法是判断当前点的上下左右是否被填过（先把所有位置都赋值成填过，再把rxc的位置赋值为未填过），如果都填过了，那么就结束。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=105;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

char g[N][N],ch,res[N][N];

int a,b,now,vis[N][N],r,c,k;

void gao(int i,int j)

{

    vis[i][j]=1;

    if(now<a+1&&b)

    {

        if(g[i][j]=='R')

            now++;

        res[i][j]=ch;

        if(now==a+1)

        {

            now=0,b--,k--;

            if(k<=0)

                return ;

            if(ch=='9')

                ch='A';

            else if(ch=='Z')

                ch='a';

            else ch++;

        }

    }

    else if(now<a&&b==0)

    {

        if(g[i][j]=='R')

            now++;

        res[i][j]=ch;

        if(now==a)

        {

            now=0;

            k--;

            if(k<=0)

                return ;

            if(ch=='9')

                ch='A';

            else if(ch=='Z')

                ch='a';

            else ch++;

        }

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t--)

    {

        memset(vis,-1,sizeof(vis));

        int cnt=0;

        cin>>r>>c>>k;

        for(int i=1; i<=r; i++)

            for(int j=1; j<=c; j++)

                vis[i][j]=0;

        for(int i=1; i<=r; i++)

        {

            cin>>g[i]+1;

            for(int j=1; j<=c; j++)

            {

                if(g[i][j]=='R')

                    cnt++;

            }

        }

        a=cnt/k,b=cnt%k,now=0;

        int L=1,R=c,U=2,D=r,i=1,j=1;

        ch='0';

        while(1)

        {

            int f=0;

            while(j<=R)

            {

                gao(i,j);

                j++;

                f=1;

            }

            if(f)

                j--;

            if(vis[i+1][j]&&vis[i-1][j]&&vis[i][j+1]&&vis[i][j-1])

                break;

            i++;

            //                cout<<"ggg:"<<i<<" "<<j<<endl;

            f=0;

            R--;

            while(i<=D)

            {

                gao(i,j);

                i++;

                f=1;

            }

            if(f)

                i--;

            if(vis[i+1][j]&&vis[i-1][j]&&vis[i][j+1]&&vis[i][j-1])

                break;

            j--;

            D--;

            //                   cout<<"gg:"<<i<<" "<<j<<endl;

            f=0;

            while(j>=L)

            {

                gao(i,j);

                j--;

                f=1;

            }

            if(f)

                j++;

            if(vis[i+1][j]&&vis[i-1][j]&&vis[i][j+1]&&vis[i][j-1])

                break;

            i--;

            L++;

            //                  cout<<"gg:"<<i<<" "<<j<<endl;

            f=0;

            while(i>=U)

            {

                gao(i,j);

                i--;

                f=1;

            }

            if(f)

                i++;

            if(vis[i+1][j]&&vis[i-1][j]&&vis[i][j+1]&&vis[i][j-1])

                break;

            j++;

            U++;

            //                  cout<<"gg:"<<i<<" "<<j<<endl;

        }

        for(int i=1; i<=r; i++)

        {

            for(int j=1; j<=c; j++)

            {

                cout<<res[i][j];

            }

            cout<<endl;

        }

    }

    return 0;

}

巴特西

CodeForces - 1255D （模拟+构造+贪心）

题意

思路

代码

最新文章

热门文章