Educational Codeforces Round 126

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
F(你真的会二分吗)

题目

https://codeforces.com/contest/1661/problem/F

给你n个线段

问最少切多少次,让切割后所有线段长度平方和不大于m

范围

n<=1e5

线段长度和 <= 1e9

m <= 1e18

7s

512MB

题解

尝试

对于最外层的答案, 显然二分答案

那么问题变成了 如果指定切割k次, 能否满足条件

贪心: 从小到大, 判断剩余期望与已切割, 显然如果 当前 乘上段数 不大于剩余值, 那么不需要切割, 否则任意不合法必定存在比当前段更大的值, 要切也是切更大的

一定不切割的状态 能证明了, 但是不是这种状态时,可能切割也可能不切割, 即使切割, 怎么计算次数也不知道

https://codeforces.com/contest/1661/submission/153691360

例如两个线段 3,4, 要结果小于17, 最好的办法是均分4, 而这种没有对应的贪心规则, 上述方法不能判断

另一个正确但是会超时的思路是

我们如果知道一个具体的段,要切割成多少份, 那么显然可以数学O(1)就算出这一段切割的最小值,(切割出来的尽量相等)

那么一个段 从 k次变成k+1次 它带来的变化量也是 上述计算相减,也是O(1)的

那么 我们直接维护优先队列 (多切割一次代价,线段编号,当前切割次数), 这样每次取最大的切一下,放回去

复杂度就是 O(线段长度和), 也能直接计算出k次最优

问题是O(线段长度和)的计算代价, 甚至说这就是枚举答案了,外层的二分都没意义了

题解

注意到 一个线段 随着切割次数变多, 每次贡献的代价也是单调递减的!!!!!!

再结合上面的 优先队列思路, 其实就是选取了k次最大值, 那么也就是 被选的 >=x, 未被选的 <= x

也就变成了找x, 满足如果被选的都是 大于x 则不满足题意,且如果被选的都是 大于等于 x 则满足题意

那么个数也就自然 是 大于x的个数,加上 与目标差距 除以 x 向上取整了

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->a;)
#define pb push_back
const double pi = acos(-1.0);

// 0 < a1 < a2 < a3..an 传送点
// 传送消耗 (ai-aj)**2 能量
// + 一些整数点 => a0 -> an 能量消耗 <= m
// 最小整数点个数

ll a[200010];
vector<ll> segs ;
int n;
ll m;

ll f(ll len, ll part){
  if(part > len)return len;
  ll minv = len/part;
  ll maxcnt = len%part;
  // printf("f(%lld %lld) => %lld %lld => %lld\n",len,part,minv,maxcnt,minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt);
  return minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt;
}

// 大于等于x的贡献都选
pair<ll,ll> calc(ll x){ // 切割次数, 消耗平方值
  assert(x > 0);
  ll cnt = 0; // 个数
  ll sum = 0; // 消耗
  rep(i,0,n){
    if(x <= 2){
      sum += f(segs[i],1) - f(segs[i],segs[i]); // 1*1*segs[i];
      cnt += segs[i] - 1;
      continue;
    }
    // 最大的都不满足
    if(f(segs[i],1) - f(segs[i],2) < x){
      continue;
    }
    // 二分切割的段
    int l = 1, r = segs[i]; // l 满足 r 不满足
    while(l+1<r){
      int mid = (l+r)/2;
      if(f(segs[i],mid) - f(segs[i],mid+1)>= x){
        l = mid;
      }else{
        r = mid;
      }
    }
    sum += f(segs[i],1) - f(segs[i],r);
    cnt += l;
  }
  return {cnt,sum};
}

int main(){
  ll cost = 0;
  scanf("%d",&n);
  rep(i,1,n+1){
    scanf("%lld",a+i);
    segs.push_back(a[i]-a[i-1]);
    cost += (a[i] - a[i-1])*(a[i] - a[i-1]);
  }
  scanf("%lld",&m);
  if(cost <= m){
    printf("0\n");
    return 0;
  }
  // 找的是 x 不是答案
  // l 满足 r 不满足
  ll l = 0, r = 1'000'000'000'000'000'000;
  while(l+1<r){
    // printf("[%lld %lld]\n",l,r);
    ll mid = (l+r)/2;
    if(calc(mid).second >= cost - m){
      l = mid;
    }else{
      r = mid;
    }
  }
  assert(l != 0);
  auto [c,s] = calc(r); // x+1 的所有
  printf("%lld\n",c + (cost - m - s)/l + !!((cost - m - s)%l));
  return 0;
}

总结

里面这个 二分好像很有用, 感觉之前做PE应该遇到过类似的,但是没想到二分,唉 我好蠢啊

数学证明

其实这里有一个东西 没有严格证明

就是 f(x,k) - f(x,k+1) 随着k增大而减小

难就难在它是整数划分, 如果是实数的话, 直接分析导数即可

dreamoon

jiangly

简单的说, 把 (x,k-1)的方案 和 (x,k+1)的方案拼在一起, 那么它一定是 2x 分割2k块的一个方案

那么 显然 (x,k)的方案的两倍 恰好是(2x,2k)的最优解

因此 2f(x,k) <= f(x,k-1) + f(x,k+1) 即

f(x,k-1) - f(x,k) >= f(x,k) - f(x,k+1) 得证

参考

https://blog.csdn.net/Code92007/article/details/124089868