有段时间没刷题了

忙着复习考试是一方面,另一方面也是确实有点怠惰了

生活还是要有点外部压力才能让自己有动力啊


CF1623C Balanced Stone Heaps

传送门

一句话题意

有若干堆石头排成一列,从第33堆开始直至第nn堆依次执行如下操作:

  1. 假设当前位于第ii堆石头
  2. 任意选取一个dd,从第ii堆中取出3d3d个石头,将其中dd个放到第i1i-1堆,2d2d个放到第i2i-2堆中

经过若干次上述操作后,最大化所有石堆中数量最少的那一堆的石头数,输出这个数

n2×105n\le 2\times 10^5

石堆大小hi109h_i\le 10^9

解法(TLDR)

考虑二分答案。对于一个确定的答案xx,从右向左考虑每次操作。对每堆石子,记录有多少石子是原有的,多少石子是移动过来的。从当前石堆中取石子时,要求移走的数量不能多于原有石子数量,也不能多于现有石子数量与答案之差。

一旦发现某堆石子现有数量不多于xx,则答案不可行,取左半边区间,否则取右半边区间

思路

最大化最小值是典型的二分答案xx,现在需要考虑如何用O(n)O(n)左右的复杂度进行检验。

如果直接按照题目中所述的从左到右的顺序进行考虑,需要考虑的地方太多,例如对hih_i进行操作时可以使其大小暂时小于xx,因为它可以被之后的石堆补充;hi1h_{i-1}可以被hi+1h_{i+1}补充;甚至hi2h_{i-2}也可以被hi1h_{i-1}补充,不一而足。

所以干脆从右往左考虑

一开始读漏题了,直接从右往左一顿搞,再读题的时候直接就没想过这个方向_(:з」∠)_

从右往左考虑,只需贪心地看当前石堆有没有多余的石子,有的话就直接向左边堆。

但需要注意的是,由于原题是从左往右进行操作,意味着从当前石堆取石子的时候,取出的石子数量不能多于原有石子数量(因为此时还没有从右边石堆取石子对当前堆造成影响)。因而若我们从右往左考虑,需要分开处理当前石堆原有的石子数量,和来自其他石堆的石子数量。

这样就解决了,复杂度O(nlogn)O(n\log n)

Code

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
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;

template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}

const int maxn=200000+100;
int T;
int n;
int h[maxn];

bool Check(int x)
{
int th[maxn],neg[maxn];
memset(neg,0,sizeof(int)*(n+1));
memcpy(th,h,sizeof(int)*(n+1));
for(int i=n;i>=3;--i)
{
if(neg[i]+th[i]<x)
return false;
else
{
int d=min(th[i]/3,(neg[i]+th[i]-x)/3);
neg[i-1]+=d;
neg[i-2]+=d*2;
}
}
if(neg[2]+th[2]<x || neg[1]+th[1]<x)
return false;
return true;
}

void Work()
{
read(n);
int l=0,r=0;
for(int i=1;i<=n;++i)
read(h[i]),r=max(r,h[i]);
int ans=-1;
while(l<=r)
{
int mid=(l+r)/2;
if(Check(mid))
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
printf("%d\n",ans);
}

int main()
{
read(T);
while(T--)
{
Work();
}
return 0;
}