CF1176C C. Beaurtiful Rectangle

发表于 | 阅读数

给你$n$($n\leq 410^5$)个数,求尽量构成一个最大的矩阵，各行各列不相同。

因为是矩阵$wh=h*w$,我们可以枚举短的那条边$w$,枚举次数=$\sqrt{n}$,然后一个数字$i$如果出现了$cnt_i$,它只能斜着放所以最多放$w$个，这样可以放置的总数就是

暴力枚举$n\sqrt{n}$
然后就是放置，像枚举时候一样斜着放

  • 应该先把$cnt_i$最多的先放。
  • 枚举时注意$w\leq h$
  • 放置时可以直接斜这放，没有放的元素=$ans[i][j+h]$
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 4e5 + 10;
const int inf = 1e9 + 7;
int a[N], li[N], n, ansn, answ, ansh;
int p[N];
int vis[N];
bool cmp(int u, int v)
{
    return vis[u] > vis[v];
}
int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), li[i] = a[i];
    int num = n;
    sort(li + 1, li + 1 + num);
    //sort(a+1,a+1+n);
    num = unique(li + 1, li + 1 + num) - li - 1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(li + 1, li + 1 + num, a[i]) - li;
    for (int i = 1; i <= n; i++)
        vis[a[i]]++;
    for (int w = 1; w * w <= n; w++)
    {
        int sum = 0;
        for (int i = 1; i <= num; i++)
            sum += min(vis[i], w);
        int h = sum / w;
        if (h < w)
            continue;
        if (h * w > ansn)
        {
            ansn = h * w;
            answ = w;
            ansh = h;
        }
    }
    printf("%d\n%d %d\n", ansn, answ, ansh);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    sort(p + 1, p + 1 + num, cmp);
    int x = 1, y = 1, cnt = 1;
    int ans[answ + 10][ansh + 10];
    memset(ans, 0, sizeof(ans));
    for (int j = 1; j <= num; j++)
    {
        int i = p[j];
        vis[i] = min(vis[i], answ);
        while (vis[i] > 0)
        {
            vis[i]--;
            ans[x][y] = li[i];
            //cout<<x<<" "<<y<<" "<<li[i]<<endl;
            if (x == answ)
                y = y - x + 2, x = 1;
            else
                x++, y++;
        }
    }
    for (int i = 1; i <= answ; i++)
    {
        for (int j = 1; j <= ansh; j++)
        {
            if (ans[i][j] != 0)
                printf("%d ", ans[i][j]);
            else
                printf("%d ", ans[i][j + ansh]);
        }

        printf("\n");
    }
}