cf950f Curfew

神贪心……写了一个晚上加一个早上。

先考虑只有一个宿管的情况。

首先，如果这个宿舍人多了，多余的人就跑到下一个宿舍。（如果这是最后一个宿舍的话，多的就躺床底下）
如果这个宿舍人少了，但是能从别的宿舍调过来人，那就调人。
如果这个宿舍人少了，从别的宿舍也调不过来足够的人，那就全跑到下一个宿舍去。
让宿管查宿。

关于调人，我们可以每次总是从当前能调过来人的最远宿舍调人，调成负的也无所谓。想一想，为什么。

还有一个神奇的事情：不同的人的路径不交。比如说，有 \(i \leq a \leq b \leq j\)，要是 \(i\) 跑到 \(b\)，\(j\) 跑到 \(a\)，就不如 \(i\) 去 \(a\)，\(j\) 去 \(b\)。

因此，有这样一个宿舍：这个宿舍左边的人都去对付第一个宿管，右边的人都去对付第二个宿管，这个宿舍的人有去对付第一个的也有去对付第二个的。

或者说，我们枚举有多少个人对付第一个宿管。每次枚举都 \(\mathrm{O}(n)\) 的求一下，总复杂度是 \(\mathrm{O}(n^2b)\)，这样不好，考虑加速枚举。

可以发现，分去对付第一个宿管的人越多，宿管发现的赖宿舍数越少。

记 \(f(m)\) 是给第一个宿管分去 \(m\) 人然后发现的赖宿舍数，显然 \(f(m)\) 是非严格单调减的。记 \(g(m)\) 是给第一个宿管分去 \(m\) 人（也就是给第二个宿管分 \(nb-m\) 人）然后第二个宿管发现的赖宿舍数，显然 \(g(m)\) 是非严格单调增的。

欲最小化 \(\max(f(m),g(m))\)，则记 \(z(m)=g(m)-f(m)\)，则 \(z(m)\) 非严格单调增。二分找出那个合适的 \(m\) 即可。

需要注意的一点是，如果 \(z(m)=0\) 那当然好，那样答案就是 \(ans(m)\)。可是我们在二分的时候写的判定是 \(z(m) \geq 0\) 这种，有可能找出来的是 \(z(m) > 0\) 的最小 \(m\)，因此还要看看 \(ans(m-1)\)，看看到底哪个更小。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int aa[100005], n, d, b, qq[100005], cur=1, a[100005], mid;

int f(int hmn, int far){

	int r=1, sum=0, re=0;

	for(int i=1; i<=hmn; i++){

		for(; r<=far && r<=i+d*i; r++)

			sum += a[r];

		if(a[i]>=b){

			int tmp=a[i]-b;

			a[i] -= tmp;

			a[i+1] += tmp;

			sum -= a[i];

		}

		else{

			if(sum>=b){

				a[r-1] -= b - a[i];

				a[i] = b;

				sum -= a[i];

			}

			else{

				a[i+1] += a[i];

				a[i] = 0;

				re++;

			}

		}

	}

	return re;

}

int z(int x, int &tmp1, int &tmp2){

	while(qq[cur-1]>=x && cur>1)	cur--;

	while(qq[cur]<x && cur<n)	cur++;

	memset(a, 0, sizeof(a));

	for(int i=1; i<=cur; i++)

		a[i] = aa[i];

	a[cur] = x - qq[cur-1];

	tmp1=f((n+1)/2, cur);

	memset(a, 0, sizeof(a));

	for(int i=n; i>=cur; i--)

		a[n-i+1] = aa[i];

	a[n-cur+1] = qq[cur] - x;

	tmp2=f(n/2, n-cur+1);

	return tmp2-tmp1;

}

int main(){

	cin>>n>>d>>b;

	for(int i=1; i<=n; i++){

		scanf("%d", &aa[i]);

		qq[i] = qq[i-1] + aa[i];

	}

	int l=0, r=n*b,  re, tmp1, tmp2;

	while(l<=r){

		mid = (l + r) >> 1;

		if(z(mid, tmp1, tmp2)>=0)	re = mid, r = mid - 1;

		else	l = mid + 1;

	}

	z(re, tmp1, tmp2);

	int ans=max(tmp1,tmp2);

	z(re-1, tmp1, tmp2);

	ans = min(ans, max(tmp1, tmp2));

	cout<<ans<<endl;

	return 0;

}

upd：从神犇代码学的

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, cnt1, cnt2, b, d;

ll a[100005];

ll sum(ll l, ll r){

	if(l<1)	l = 1;

	if(r>n)	r = n;

	return a[r] - a[l-1];

}

int main(){

	cin>>n>>d>>b;

	for(int i=1; i<=n; i++){

		scanf("%I64d", &a[i]);

		a[i] += a[i-1];

	}

	for(int i=1; i<=n/2; i++){

		if(sum(1, i+(ll)i*d)>=(ll)(cnt1+1)*b)	cnt1++;

		if(sum(n-i-(ll)i*d+1, n)>=(ll)(cnt2+1)*b)	cnt2++;

	}

	cout<<max(n/2-cnt1, n/2-cnt2);

	return 0;

}

巴特西

cf950f Curfew

最新文章

热门文章