You are given 𝑛 integers. You need to choose a subset and put the chosen numbers in a beautiful rectangle (rectangular matrix). Each chosen number should occupy one of its rectangle cells, each cell must be filled with exactly one chosen number. Some of the 𝑛 numbers may not be chosen.

A rectangle (rectangular matrix) is called beautiful if in each row and in each column all values are different.

What is the largest (by the total number of cells) beautiful rectangle you can construct? Print the rectangle itself.

链接🔗

「CodeForces 1277F」Beautiful Rectangle

题解

比较麻烦的构造题
假设行一定小于列,于是我们枚举行 x,然后考虑我们的数是否能构成大于 x*x 的矩阵
然后统计最大的数量 ,确定行和列
再用阶梯的形式去构造该矩阵

代码

const ll maxd = 4e5+10;

ll cnt[maxd],n,ans[maxd];
map<ll,ll> mp;
vector<P> a;
bool cmp(const P a,const P b)
{
    return a.ND > b.ND;
}
int main()
{
//    __IN;__OUT;
    RLL(n);
    FOR(i,1,n)
    {
        ll x;RLL(x);
        mp[x]++;
    }
    for(auto p:mp) a.pb(p);
    sort(all(a),cmp);
    for(auto x:a) cnt[x.ND]++;

    //确定行数和最大摆放数量
    ll now = a.size(),mx = 0,row = 0, sum = 0;
    for(int i=1;i *i<=n;i++)
    {
        sum+= cnt[i] * i;
        now -= cnt[i];
        ll t = now * i + sum;
        if(t < i * i) continue; // 数不够
        if(t / i * i > mx) mx = t/i*i,row = i; //如果选出的最大数量多于当前值,则更新
    }
    // 构造方案
    ll col = mx / row , x = 1, y =1;
    FOR(i,1,a.size())
    {
        ll num = min(row,a[i-1].ND);
        while(num--)
        {
            ans[(x-1)*col + y] = a[i-1].first;
            x = (x %row) + 1, y = (y%col) + 1;
            if(ans[(x-1) * col + y]) y = (y%col) + 1;
        }
    }
    PLN(mx);PLP(row); PLN(col);
    FOR(i,1,row)
        FOR(j,1,col)
            if(j== col)  PLN(ans[(i-1) * col +j]);
            else PLP(ans[(i-1) * col +j]);
    return 0;
}