Codeforces Round 908

發表於 更新於 分類於 ， Disqus： 文章字數： 792 所需閱讀時間 ≈ 3 分鐘
D(构造,贪心)E()

https://codeforces.com/contest/1893

n个 有色块, 第i个颜色$a_i$

安排它们到m个书架, 第i个书架 能放s_i个, $\sum s_{1\dots m} = n$

colorfulness(一个书架) = 该书架上同色块的最近距离(index差), 如果全部不同色则等于s_i

对于书架i有colorfulness下限di需求

提供摆放方案, 或者判断无法满足需求

m,n 2e5

3s

512mb

我的思路

下限的意思就是越大越好

确定了一个书架上放哪些块,那么????

好像一个书架上都没有什么想法

那就按照下限做, 先放个数最多的,然后它就按照下限要求放间隔

问题是 8容量,但是间隔下限要求3, wxyzwxyz是方案

但按照 下限要求 wxywxyzz 会卡住

题解

啊 贪心 啊

对于长度s(例如15),最小间隔要求k(例如4)的按k拆分

[....][....][....][...]

必要条件 每段里面两两不同

从后向前放 [....][...], 如果相邻段有相同的值出现, 则前面的根据后面的位置放置

例如 [.X..][.X.]

所以 每段里面两两不同, 是 充分条件

问题变成给了很多 长度的段

要每段里面放两两不同的颜色, 是否有方法放满

而这个问题 就简单, 贪就完了

sort 段剩余长度

for 颜色c 从大到小

最大的c个长度 减1, 模拟就没了

代码

https://codeforces.com/contest/1893/submission/234331370

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
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(int)(n);i++)
#define per(i,a,n) for(int i=(n);i-->(int)(a);)
int read(){int r;scanf("%d",&r);return r;}
const int N=200000;
template<class T> using maxPQ = priority_queue<T,vector<T>>;
int a[N+10];
int s[N+10];
int d[N+10];
void w(){
  int n=read();
  int m=read();
  rep(i,0,n) a[i]=read();
  rep(i,0,m) s[i]=read();
  rep(i,0,m) d[i]=read();
  vector<vector<int> > ans(m);
  rep(i,0,m) ans[i].resize(s[i],0);
  maxPQ< array<int,4> > pq; // { len, shelf id, t-th seg, off }[]
  int maxl = 0;
  rep(i,0,m) {
    int S = s[i];
    int D = d[i];
    maxl = max(maxl, D);
    rep(t,0,S/D) pq.push({D, i, t, 0});
    if(S%D != 0) pq.push({S%D, i, S/D, 0});
  }
  sort(a,a+n);
  vector<pair<int,int> > cc; // { count, color }
  rep(i,0,n) {
    if(i == 0 or cc.back().second != a[i]) {
      cc.push_back({1, a[i]});
    }else{
      cc.back().first++;
    }
  }
  sort(begin(cc),end(cc));
  per(i,0,size(cc)){
    auto [cnt,color] = cc[i];
    if((int)pq.size() < cnt) {
      printf("-1\n");
      return ;
    }
    vector<array<int,4> > add;
    rep(j,0,cnt) {
      auto [len,shelf_id,t,off] = pq.top();
      pq.pop();
      ans[shelf_id][t * d[shelf_id] + off] = color;
      if(len > 1) add.push_back({len-1,shelf_id,t,off+1});
    }
    for(auto o:add) pq.push(o);
  }
  // fix order
  rep(i,0,m) {
    map<int,int> v2pos;
    per(t,0,s[i]/d[i] + !!(s[i]%d[i])) {
      vector<int> vals;
      rep(j,0,d[i]) {
        int idx = t*d[i]+j;
        if(idx >= s[i]) break;
        vals.push_back(ans[i][idx]);
        ans[i][idx] = -1;
      }
      per(j,0,size(vals)){
        int v = vals[j];
        if(v2pos.count(v) and v2pos[v]/d[i] == t+1){
          ans[i][v2pos[v] - d[i]] = v;
          swap(vals[j],vals.back());
          vals.pop_back();
        }
      }
      rep(j,0,d[i]) {
        int idx = t*d[i]+j;
        if(idx >= s[i]) break;
        if(ans[i][idx] == -1) {
          ans[i][idx] = *vals.begin();
          vals.erase(vals.begin());
        }
        v2pos[ans[i][idx]] = idx;
      }
    }
    for(auto v:ans[i]) printf("%d ",v);
    printf("\n");
  }
}

int main() {
  int t=read();
  while(t--) w();
  return 0;
}

总结

这个拆断 的充要性 事后诸葛看起来还真显然, 但自己就是想不到

参考

官方题解