洛谷3571 POI2014 SUP-Supercomputer （斜率优化）

一道神仙好题。

首先看到有多组$k$，第一反应就是离线。

考虑贪心。

我们每次一定是尽量选择有儿子的节点。以便于我们下一次扩展。

但是对于一个$k$，每次贪心的复杂度是$O(n)$

总复杂度是$O(nq)$，肯定过不了。

qwq

那我们只能来考虑一个快速求一个$k$的答案。

感觉题解的柿子好神仙啊。

这里定义$f[i]$表示$k=i$的时候的最小次数。

$sum[i]$表示深度大于等于$i$的点有多少个。

则$$f[i]=max(j+\lceil \frac{sum[j+1]}{i} \rceil)$$

含义是用了$i$次把全$i$层都取掉，然后剩下的每次都能取满。

qwq现在来解释一下为什么是这个柿子。

首先，比较容易证明答案一定在所有的$(j+\lceil \frac{sum[j+1]}{i} \rceil$中，因为这已经是最优情况了（前i次最多取i层，而后面也是每次取满，所以一定是最优的情况，不存在更优秀的情况。）

那么为什么是要取$max$呢。

是为了避免不合法的情况。

这里不合法的情况有两种情况，首先是前$i$次取不满$前i层$。那么如果存在这个情况，一定存在$j$使得，前$j$层能够$j$次取满，但是$j到i$不能用$j-i$取满，则存在等式

\[\lceil \frac{sum[j+1]}{k} \rceil > \lceil \frac{sum[i+1]}{k} \rceil + (i-j)
\]

\[\lceil \frac{sum[j+1]}{k} \rceil + j> \lceil \frac{sum[i+1]}{k} \rceil + i
\]

那么取$max$，这种不合法的情况就能排除。

另一种不合法的情况就是，后面的次数并不能每次都取满。

如果上面的情况合法，那么一定存在$$\lceil \frac{sum[i+1]-sum[i+x+1]}{k} \rceil + i+x+1 > \lceil \frac{sum[i+1]}{k} \rceil + i$$

因为存在一层满足不能够一次用满k，且没有多余的东西让他选，那这时候等式左边的$i+x+1$等于该层的时候，一定比原本的柿子更大。

至于为什么不存在一个小于$max$并且合法的情况，是因为一层最少需要一次。而如果存在$min$，说明要满足用小于$j$次，选完$j$层，而这个东西是不可能的。

qwq

那么证明到这里，大概能说明上述的柿子的是对的了。

也就是

\[f[i]=max(j+\lceil \frac{sum[j+1]}{i} \rceil)
\]

那接下来应该怎么优化呢。

我们将上述柿子进行变形

\[f[i]=max(\lceil \frac{j\times i+ sum[j+1]}{i} \rceil)
\]

那么如果存在一个$j>k$且$j比k$优秀的话，应该满足

\[j\times i + sum[j+1] > k \times i + sum[k+1]
\]

经过化简，$$\frac{sum[j+1]-sum[k+1]}{j-k}>-i$$

直接上斜率优化就好

$sum$数组可以直接通过前缀和求出来

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk make_pair

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 1e6+1e2;

int sum[maxn];

int n,m;

int point[maxn],nxt[maxn],to[maxn];

int cnt;

int deep[maxn];

int dp[maxn];

int a[maxn];

void addedge(int x,int y)

{

	nxt[++cnt]=point[x];

	to[cnt]=y;

	point[x]=cnt;

}

struct Point{

	ll x,y,num;

};

Point q[maxn];

ll chacheng(Point x,Point y)

{

	return x.x*y.y-x.y*y.x;

}

bool Count(Point i,Point j,Point k)

{

	Point x,y;

	x.x=k.x-i.x;

	x.y=k.y-i.y;

	y.x=k.x-j.x;

	y.y=k.y-j.y;

	if (chacheng(x,y)>=0) return true;

	return false;

}

int head=1,tail=0;

void push(Point x)

{

	while(tail>=head+1 && Count(q[tail-1],q[tail],x)) tail--;

	q[++tail]=x;

}

void pop(int lim)

{

	while(tail>=head+1 && q[head+1].y-q[head].y>lim*(q[head+1].x-q[head].x)) head++;

}

int mx;

void dfs(int x,int dep)

{

	deep[dep]++;

	mx=max(mx,dep);

	for (int i=point[x];i;i=nxt[i])

	{

		int p = to[i];

		dfs(p,dep+1);

	}

}

int qq;

int main()

{

  n=read();qq=read();

  int ymh =0;

  for (int i=1;i<=qq;i++) a[i]=read(),ymh=max(ymh,a[i]);

  for (int i=2;i<=n;i++)

  {

  	 int x=read();

  	 addedge(x,i);

  }

  dfs(1,1);

  for (int i=mx;i>=0;i--)

  {

  	deep[i]+=deep[i+1];

  }

  for (int i=0;i<mx;i++)

    push((Point){i,deep[i+1],i});

  for (register int i=1;i<=ymh;++i)

  {

  	pop((-1)*i);

  	int now = q[head].num;

  	dp[i]=now+((deep[now+1]-1)/i)+1;

  }

  for (int i=1;i<=qq;i++) cout<<dp[a[i]]<<" ";

  return 0;

}

巴特西

洛谷3571 POI2014 SUP-Supercomputer （斜率优化）

最新文章

热门文章