codeforces-Ed86-D
题意
有n个数 m[i] 每个数小于k
要求分成最少组 每个组内大于等于 i(1~k) 的数不超过c[i]
首先要求出最小分组 q
引入新数组 ar，让 ar[i] 表示数组 m 中大于等于 i 的数字的个数
又因为 c[i] 数组表示每个分组大于等于 i 的数字的最大个数
所以就能得到，单对于数字 i 而言，最小分组数为 ar[i] 除以 c[i] 向上取整
写作 ceil(1.0*ar[i]/c[i]) 或者 (ar[i]+c[i]-1)/c[i]
最后，让答案分组 q 在这些最小分组中取大即可
得出最小分组 q 后
贪心可得，将数组 m 进行排序后
将 m[1], m[2], m[3]… m[n] 循环放入组 T[1], T[2] … T[q], T[1], T[2] … 即可得出分组方案
//为什么一定要这样分成q组 对于q=max{(i=1~k) | ceil(1.0 × ar[i]/c[i] ) } 所以每组有m/q<= m/ceil(1.0×ar[i]/c[i]) {i=1~k} 个数 不会超过任意一个 c[i]限制 。
//为什么一定需要排序后循环放入T？不能理解
//分成q组后从大到小放入后放入的限制比先放入的宽一定可以放入
//且取余q一定不会超过最短的连续相等的c[m[i]]长度这样才能保证不冲突
//https://blog.csdn.net/tourist1412/article/details/105792592
即对于第 i 组 T[i] 而言，它所包含的数为 m[i], m[q+i], m[2q+i], m[3q+i] …
根据上面对于 q 的解法，能够保证同一组中的数不会与题意产生冲突
ps. 虽然根据 ar 和 c 数组的定义，m 数组应该是从大到小排序后，从较大的数字开始循环放入的，但实际上从小到大也是可行
很明显可以想到，尽量满足i值大的数最优。因为i越大,c[i]越小，限制既然越大，那么先安排，后面再让限制小的插入。用一个优先队列维护
//贪心实现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
using namespace std;
typedef long long ll;
const ll Max=2e5+5;
int data[Max];
int c[Max],maxc[Max];
bool cmp(int a,int b){return a>b;}
int main(){
//TurnoffIO;
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>data[i],maxc[data[i]]++;
for(int i=1;i<=m;i++)cin>>c[i];
sort(data+1,data+1+n);
int up=0;
for(int i=m;i>0;i--){
maxc[i]+=maxc[i+1];
up=max(up,(int)ceil(1.0*maxc[i]/c[i]));
}
vector<int>ans[up];
for(int i=1;i<=n;i++)ans[i%up].push_back(data[i]);
cout<<up<<endl;
for(int i=0;i<up;i++){
cout<<ans[i].size()<<" ";
for(auto p:ans[i])cout<<p<<" ";
cout<<endl;
}
}
///优先队列 对指定struct 使用优先队列 实现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
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int c[maxn],b[maxn];
struct Node {
vector<int>a;
int cnt;
bool operator < (const Node &rhs)const {
return cnt > rhs.cnt;
}
};
int main() {
std::ios::sync_with_stdio(false);
int n,k;
cin >> n >> k;
for(int i = 1;i <= n;i++) {
cin >> b[i];
}
for(int i = 1;i <= k;i++) {
cin >> c[i];
}
sort(b + 1,b + 1 + n);
priority_queue<Node>q;
Node a;
a.cnt = 0;a.a.clear();
q.push(a);
for(int i = n;i >= 1;i--) {
Node now = q.top();q.pop();
if(now.cnt < c[b[i]]) {
while(now.cnt < c[b[i]]) {
now.a.push_back(b[i]);
now.cnt++;
i--;
}
i++;
q.push(now);
}
else {
Node tmp;
tmp.cnt = 0;
while(tmp.cnt < c[b[i]]) {
tmp.cnt++;
tmp.a.push_back(b[i]);
i--;
}
i++;
q.push(tmp);
q.push(now);
}
}
cout << q.size() << endl;
while(!q.empty()) {
Node now = q.top();q.pop();
cout << now.cnt << ' ';
for(int i = 0;i < now.cnt;i++) {
cout << now.a[i] << ' ';
}
cout << endl;
}
return 0;
}
//同样的贪心放入
上一个思路极端情况需要每次把已使用并且还能使用的背包拿去放物品，也就是把已开始使用的背包循环了一遍，所以我们可以直接在二重循环上优化，优化方法就是如果c[m[i]] > c[m[i + 1]]才重新从第一个背包开始装，不然从上次的背包开始继续装（很好理解，如果相等，那么前面的背包已经装满了，没必要从第一个背包开始去试）
1 |
|
//二分法
假设t个背包能装下所有的物品,那么 t+1个背包一定也能装下所有的物品,满足二分性质,所以可以通过二分先求出最小的背包数量.
怎么check呢?
对于每一个 c[i],如果大于等于c[i]的物品要大于 mid*c[i]
那么当前的背包数量肯定是不满足答案的.
放物品非常简单,对物品的重量排序,然后每个背包轮流放一个即可
1 |
|