P3566 [POI2014] KLO-Bricks 题解

题意

题目传送门

给定一些砖块和他们的数量，求把所有砖块排成一排，且相邻两砖块两两不同的任意一个合法方案。其中，一行的头和尾已经确定。

思路

用贪心策略，每次先取数量最多的那种砖块。

可是要是最后一个砖块与倒数第二个重合了呢？

于是，在有两种相同数量砖块的前提下，优先选与最后一个给定砖块种类相同的那种砖块。

要是在这种情况下都不合法，就直接结束了。

所以考虑使用优先队列。

每次都取前两个，若第一个不行就取第二个。$ans_{sum}=ans_{sum-1}$ 的情况最后再判。

代码

#include <cstdio>
#include <queue>
using namespace std;
int k, P, Q, x, sum;
int ans[1000001];
struct node {
	int col, num;
	bool operator < (const node &a) const {
		if (num == a.num) return a.col == Q; // 与最后一个颜色相同的优先选
		return num < a.num; // 数量多的优先选
	}
};
int main() {
	scanf("%d%d%d", &k, &P, &Q);
	if (k == 1) // 一定要特判！
		return scanf("%d", &x),
			   printf("%d", x == 1 && P == 1 && Q == 1), 0;
	priority_queue <node> q;
	for (int i = 1; i <= k; i++) {
		scanf("%d", &x);
		sum += x; // 求总和
		if (i == P) x--; // 用掉了一个
		if (i == Q) x--; // 用掉了一个
		if (x < 0) // 没有足够砖块，肯定不行
			return printf("0"), 0;
		if (x) q.push({i, x});
	}
	ans[1] = P, ans[sum] = Q;
	for (int i = 2; i < sum; i++) {
		node x = {0, 0};
		node y = {0, 0};
		if (!q.empty())
			x = q.top(),
			q.pop();
		if (!q.empty())
			y = q.top(),
			q.pop();
		if (x.col == ans[i - 1]) { // 第一个不合法
			if (!y.num) // 只有一种砖块了，不行
				return printf("0"), 0;
			ans[i] = y.col, y.num--; // 用砖块
		} else {
			if (!x.num)
				return printf("0"), 0;
			ans[i] = x.col, x.num--;
		}
		if (x.num) q.push(x); // 重新进队列
		if (y.num) q.push(y); // 重新进队列
	}
	if (ans[sum - 1] == ans[sum])
		return printf("0"), 0; // 特判
	for (int i = 1; i < sum; i++)
		printf("%d ", ans[i]);
	printf("%d", ans[sum]); // 坑输出格式
	return 0;
}

全网唯一 一篇O(n)题解+bzoj/luogu最优解

(截止2018.10.31)

这个题看大家都是优先队列，然后直接贪心放置。

还有用权值线段树来模拟堆过的%%%。

其实不用带logn也可以过的。

大家的方法是从左往右扫过去的。

对于这种插空排序的问题，还有一种考虑方法就是每个种类每个种类来考虑。

好处是，前面放过的种类放完了，和当前第i种永远不会产生冲突。

这就是我的大方向思路。

一、先不考虑端点固定的情况。

其实，不一定要先放最多的。

顺序可以随便。

假设放到完了前i种，那么，一共有sum[i]个。

对于后面的n-i种来说，前i种的方法对后面没有影响。

所以，肯定前i种放法中，选择相邻的情况最少的方案咯！

怎样凑出这个方案？

放完了前i种，设还剩下k个相邻位置。

1.对于第i种，肯定先插那k个位置中。这样每次相邻的-1,已经最优。

2.如果i种还剩下，那就从前面开始插空（不能和1中放的相邻）。这样相邻的数量不增不减。已经最优。

3.如果还剩下，那没有办法了。为了之后好处理，我们都把这些剩下的都放在末尾。

这样，不管你是数量较多的，还是数量较少的，

较多的，可以放在一起，由后面的再插空隔开。

较少的，就隔开之前相邻的。

至于怎么插空？

用一个最普通的链表就可以维护。

当然，我们每次要维护3中，开始连续的那一串的起始位置。方便下次直接访问。

二、有固定点呢？

两个端点比较麻烦。

所以我们就先放端点好了。

放的方法和上面差不多。

先放p，再放q

如果p的数量大于等于q。

那么放q的时候，直接插空，然后无论如何留下一个放末尾。

如果p的数量小于q。

那么放q的时候，插完空，直接往后放完即可。

（注意的是，这样的话有一个情况，就是在最后一个和倒数第二个之间还要插一个，后面放的时候特判一下）

然后放剩下k-2种。

按照刚才的策略即可。注意不能放在1前面，以及最后一个后面。

由于策略一直是最优的。

所以放完了之后，还有相邻元素，那就无解了。

三、一些细节

1.可能有两个端点颜色相同的情况。特判即可。bzoj上还有端点相同，且这个颜色只有一个的数据。。。。

2.刚才“二”中说的那个注意事项。

3.乱七八糟的各种边界情况和+1-1等等。

画个示意图就好理解了。

代码：

全程链表，所以复杂度线性。

（其实应该还有很多常数优化空间2333）

（这个题输入输出优化都很有用，输出优化快了400ms？？？）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#define reg register int
#define il inline
#define numb (ch^'0')
using namespace std;
typedef long long ll;
const int N=1000000+5;
int nxt[N],id[N];//nxt后继，id颜色编号
int tot;
int k,p,q;
int a[N];
il void rd(int &x){
	char ch;x=0;
	while(!isdigit(ch=getchar()));
	for(x=numb;isdigit(ch=getchar());x=x*10+numb);
}
il void prin(int x){
	if(x/10) prin(x/10);
	putchar(x%10+'0');
}
il void upda(int o,int to,int d){//初始化链表元素
	nxt[o]=to;id[o]=d;
}
int main(){
	rd(k);rd(p);rd(q);
	for(reg i=1;i<=k;++i)rd(a[i]);
	if(p==q&&a[p]==1){//特判一个点
		if(k>1) printf("0");
		else printf("%d",p);
		return 0;
	}
	int las=0;
	for(reg i=1;i<=a[p];++i){//放p
		upda(++tot,0,p);
		if(las) nxt[las]=tot;las=tot;
	}
	las=1;
	int pos=0;//pos是每一次最后的连续一部分同种相邻颜色的起始位置
	if(p!=q){//放q
		int i;
		for(i=1;i<=a[q]-1&&las<=a[p];++i){
			upda(++tot,nxt[las],q);
			nxt[las]=tot;++las;
		}
		if(a[p]>=a[q]){
			nxt[a[p]]=++tot;
			upda(tot,0,q);
			pos=a[q];
		}
		else{
			pos=tot;
			while(i<=a[q]){
				nxt[tot]=tot+1;
				upda(++tot,0,q);
				++i;
			}
		}
	}
	else{
		pos=1;
	}
	int nd=tot;//末尾的编号
	for(reg i=1;i<=k;++i){//放其他的
		if(i==p||i==q) continue;
		int tmp=a[i];
		while(a[i]&&nxt[pos]!=nd){//插后面的空
			upda(++tot,nxt[pos],i);
			nxt[pos]=tot;
			a[i]--;++pos;
		}
		if(a[i]&&nxt[pos]==nd&&id[pos]==q){//细节2
			upda(++tot,nxt[pos],i);
			nxt[pos]=tot;
			pos=tot;//warning!!!
			a[i]--;
		}
		if(a[i]){//从前面插空
			int now=1;//start from a[p]
			while(a[i]&&id[nxt[now]]!=i&&nxt[now]!=nd){
				upda(++tot,nxt[now],i);
				int to=nxt[now];
				nxt[now]=tot;
				now=to;
				a[i]--;
			}
			if(a[i]){//如果还有剩余
				int las=pos;
				if(id[pos]!=i) pos=tot+1;//warning!!! tot+1
				while(a[i]){
					upda(++tot,nxt[las],i);
					nxt[las]=tot;
					las=tot;
					a[i]--;
				}
			}
		}
	}
	for(reg i=1;i!=nd;i=nxt[i]){//判断不合法
		if(id[i]==id[nxt[i]]){
			printf("0");return 0;
		}
	}
	for(reg i=1;i!=nd;i=nxt[i]){
		prin(id[i]);putchar(' ');
	}prin(id[nd]);
	return 0;
}

总结：

注意处理排序插空问题的两个大方法：

1.从左到右扫描。期间往往用数据结构维护。

2.分类别，同一个类别一起考虑。往往用到对插入的物品排序（当然本题不用）