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

佚名 6年前 (2019-11-28) 算法 2318人围观抢沙发百度已收录

题意

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路

如果农场一共有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;
}