CF1276C Beautiful Rectangle
题意
题解
显然出现次数最多的数出现次数一定小于行,这个时候列数也一定要大于行数,不然放不下
按出现次数将每个数排序
考虑从大到小枚举行,每次最大化列数
对于每个数,按从大到小的顺序把大于行数的减掉,同时更新可用的元素
显然你从大到小枚举的行,现在用不到的以后也用不到了
由于每个元素只会删一次,所以是O(n)的
填数的时候斜着填
代码如下
#include<bits/stdc++.h> using namespace std; #define re register inline int read() { int x = 0,f = 1; char ch; do { ch = getchar(); if(ch == '-') f = -1; }while(ch < '0'||ch > '9'); do { x = (x<<3) + (x<<1) + ch - '0'; ch = getchar(); }while(ch >='0' && ch <='9'); return f*x; } const int MAXN = 4e5 + 10; int n; int a[MAXN]; int b[MAXN],sum; map<int,int>vis; int tot; int ansx,ansy; pair<int,int>c[MAXN]; int M[MAXN]; int res; int main() { n = read(); for(int i=1;i<=n;i++) a[i] = read(); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { if(a[i]!=a[i-1]) b[i] = ++sum; else b[i] = sum; vis[b[i]] = a[i]; } for(int i=1;i<=sum;i++) c[i].second = i; for(int i=1;i<=n;i++) c[b[i]].first++; sort(c+1,c+sum+1);tot = n; for(int i=n;i>=1;i--) { for(int j=sum;j&&c[j].first>i;j--) { c[j].first--; tot--; } int p = tot / i; if(p < i) continue; if(res < p * i) { res = p * i; ansx = i,ansy = p; } } for(int i=1;i<=sum;i++) { c[i].first = 0;c[i].second = i; } for(int i=1;i<=n;i++) c[b[i]].first++; cout << res << endl << ansx << " " <<ansy << endl; sort(c+1,c+sum+1); for(int i=sum;i>=1;i--) { if(c[i].first>=ansx) c[i].first = ansx; else break; } int p = sum; for(int i=1;i<=ansy;i++) { for(int j=1;j<=ansx;j++) { if(c[p].first==0) p--; M[(j-1)*ansy+(i+j)%ansy+1] = vis[c[p].second]; c[p].first--; } } for(int i=1;i<=res;i++) { cout << M[i] << " "; if(i%ansy==0) cout << endl; } }