[CC-INVENTRY]Arranging the Inventory

题目大意：

有一排长度为\(n(\sum n\le10^6)\)的格子，有些格子是空的，有些格子上有一个箱子。现在你要用最小的操作把箱子都移到最左边。

每次可以进行下列两种操作：

如果第\(i,i+2\)格为空，第\(i+1\)格有箱子，则可以站在第\(i+2\)格将箱子向左推一格（.#.\(\to\)#..）
如果第\(i+1,i+2\)格为空，第\(i\)格有箱子，则可以站在第\(i+1\)格将箱子向右拉一格（#..\(\to\).#.）

输出最小的步数或说明无解。

思路：

除了已经在最左端的部分，对于一段连续的#。显然要先将其展开成#.#.#.#.的形式，然后才能往左推。\(\mathcal O(n)\)模拟即可。

源代码：

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstring>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

inline bool check(const char &ch) {

	return ch=='.'||ch=='#';

}

inline bool getval() {

	register char ch;

	while(!check(ch=getchar()));

	return ch=='#';

}

typedef long long int64;

const int N=1e5+1;

int p[N];

int main() {

	for(register int T=getint();T;T--) {

		const int n=getint();

		int m=0;

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

			if(getval()) p[++m]=i;

		}

		int64 ans=0;

		int q;

		for(q=1;p[q]==q;q++);

		for(register int i=q;i<=m;i++) {

			if(p[i-1]+2>p[i]) {

				ans+=p[i-1]+2-p[i];

				p[i]=p[i-1]+2;

			}

			ans+=p[i]-i;

		}

		if(q<=n&&p[m]>=n) {

			puts("-1");

			continue;

		}

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

	}

	return 0;

}

巴特西

[CC-INVENTRY]Arranging the Inventory

[CC-INVENTRY]Arranging the Inventory

题目大意：

思路：

源代码：

最新文章

热门文章