【BZOJ】1119: [POI2009]SLO

题意

长度为\(n(1 \le n \le 1000000)\)的账单，\(+\)表示存1，\(-\)表示取1，任意时刻存款不会为负。初始有\(p\)，最终有\(q\)。每一次可以耗时\(x\)将某位取反，耗时\(y\)将最后一个移到最前面，求最小耗时使得账单正确。

分析

首先很显然最终\(+\)和\(-\)的数目是可以确定的。

所以我们把账单按照每一个开头扫一遍就行了。

题解

将账单拓展成\(2n\)，然后从\(2\)扫到\(n+1\)，求以这个开头的最小费用。

对于\(i\)开头的，我们只需要在\(i\)到\(i+n-1\)的账单修改成数目正确的\(+\)和数目正确的\(-\)即可。怎么修改呢？目前我们只需要保证不会出现负数即可。也就是前缀和中没有负数。所以我们找到第一个前缀和最小的位置\(j\)。如果\(s_j\)小于0，则表示在\(i\)到\(j\)需要将\(\left \lceil \frac{-s_j}{2} \right \rceil\)个负的改成正的。然后再根据\(+\)和\(-\)的最终个数和当前个数计算一下费用即可。

求一个区间的最小值可以用单调队列，所以复杂度\(O(n)\)

#include <bits/stdc++.h>

using namespace std;

inline int getint() {

	int x=0, c=getchar();

	for(; c<48||c>57; c=getchar());

	for(; c>47&&c<58; x=x*10+c-48, c=getchar());

	return x;

}

const int N=100005;

int a[N], b[N], s[35], c[35];

int main() {

	int n=getint(), m=getint();

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

		a[i]=getint();

	}

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

		b[i]=getint();

	}

	sort(b+1, b+1+m);

	int tot=0;

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

		if(b[i]!=b[i-1]) {

			b[++tot]=b[i];

		}

		++s[tot];

	}

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

		for(int j=tot; j; --j) {

			c[j]+=a[i]/b[j];

			a[i]%=b[j];

		}

	}

	int ans=0;

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

		for(int j=i+1; j<=tot && s[i]>c[i]; ++j) {

			int cost=b[j]/b[i], rest=s[i]-c[i], need=(rest+cost-1)/cost;

			if(need<=c[j]) {

				c[j]-=need;

				rest=(need*cost-rest)*b[i];

				c[i]=s[i];

				for(int k=j; k>i; --k) {

					c[k]+=rest/b[k];

					rest%=b[k];

				}

			}

			else {

				c[i]+=c[j]*cost; c[j]=0;

			}

		}

		ans+=min(s[i], c[i]);

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

【BZOJ】1119: [POI2009]SLO

题意

分析

题解

最新文章

热门文章