CF10B题解

ncwzdlsd · 2023-11-03 10:10:46 · 题解

暴力。

先考虑一个贪心策略：坐在一行的一波人一定是挨着的，因为同一行的一波人坐得越分散每个人到中心点的曼哈顿距离就越大。

对于每一波人，枚举坐在哪一行、坐在该行的起始位置，然后判断能否坐下即可。

时间复杂度 O(NK^3)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool vis[1005][1005];

int main()
{
    int N,K;cin>>N>>K;
    int cc=(K+1)/2;
    while(N--)
    {
        int ans=INT_MAX,M;cin>>M;
        int x=1,yl=1;
        for(int i=1;i<=K;i++)
            for(int j=1;j<=K-M+1;j++)
            {
                bool flag=1;
                int tmp=0;
                for(int l=j;l<=j+M-1;l++)
                {
                    if(vis[i][l]){flag=0;break;}
                    else tmp+=abs(i-cc)+abs(l-cc);
                }
                if(flag&&tmp<ans) ans=tmp,x=i,yl=j;
            }
        if(ans==INT_MAX) cout<<"-1\n";
        else 
        {
            cout<<x<<' '<<yl<<' '<<(yl+M-1)<<'\n';
            for(int i=yl;i<=yl+M-1;i++) vis[x][i]=1;
        }
    }
    return 0;
}