CCF 201809-4 再卖菜

算法练习
字数统计: 2.5k   |   阅读时长≈ 11 分钟

出自CCF 201809-4 再卖菜，本文提供了两种思路解决此问题。主要涉及差分约束的解决策略以及搜索 + 剪枝操作方案。

题面

时间限制： 1.0s
内存限制： 256.0MB
问题描述：

　　在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。
　　第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。
　　注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。
　　给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。
　　字典序大小的定义：对于两个不同的价格序列(a1, a2, …, an)和(b1, b2, b3, …, bn)，若存在i(i>=1), 使得ai<bi，且对于所有j<i，aj=bj，则认为第一个序列的字典序小于第二个序列。

输入格式

　　输入的第一行包含一个整数n，表示商店的数量。
　　第二行包含n个正整数，依次表示每个商店第二天的菜价。

输出格式

　　输出一行，包含n个正整数，依次表示每个商店第一天的菜价。

样例输入

　　8
　　2 2 1 3 4 9 10 13

样例输出

　　2 2 2 1 6 5 16 10

数据规模和约定

　　对于30%的评测用例，2<=n<=5，第二天每个商店的菜价为不超过10的正整数；
　　对于60%的评测用例，2<=n<=20，第二天每个商店的菜价为不超过100的正整数；
　　对于所有评测用例，2<=n<=300，第二天每个商店的菜价为不超过100的正整数。
　　请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

思路

这道题是非常经典的最短路解差分约束问题。首先，这道题要求字典序最小，我们考虑将所有的不等式都变成 \(x_i-x_j \geq k\)，反过来求最长路即可。

首先分析为什么差分约束可以用最短路求解：
因为只有二元一次的不等式建立的差分约束才能用最短路求解，因为图中的两个点是一一对应建立关系的。
举个例子，对于 \(x_j-x_i \leq k\)，这样的不等式非常像最短路的松弛操作。假设我们有两个点, \(i\)和\(j\)，在最短路中会有转移方程 if(dist[j]-dist[i] > k) dist[j]=dist[i]+k 。我们可以发现，当前\(i\)到\(j\)有一条边权值为k，这是相当于对\(j\)更新。原来的dist[j]不满足约束条件，也就是 dist[j]-dist[i]>k，更新后一定满足约束条件，更新后的dist[j]就满足dist[j]-dist[i]<=k，而dist[i]就相当于 \(x_i\)，也就是 \(x_j-x_i \leq k\)。而且这个更新后得到的序列是字典序最大的。为什么？很简单，因为当dist[j]-dist[i]>k时让dist[j]-dist[i]<=k，dist[j]可以更新到dist[i]+k-n，n可以取任意正整数都可以满足条件，但这里的更新就相当于n取零，使得dist[j]有最大值。

然而这道题要求字典序最小，我们只需要把所有不等式都变成 \(x_i-x_j \geq k\)，反过来求最长路即可，其原理同最短路。

设第二天的第 \(i\) 家店的价格是 \(a_i\)，那么第一天第 \(i\) 家店的价格为 \(x_i\)。我们已知 \(a_i\) 的序列，要求 \(x_i\) 的最小字典序。
首先，我们可以得到的关系有:

由于题意为去尾法取整，因此可以将上述关系进一步转化为：

进一步的，我们将此关系改写为不等式约束：

接下来分析建图问题：

首先这里涉及到多项式之和，但是差分约束系统是二元一次不等式，所以我们需要对其进行重构造。这里设 \(s_i\) 为0到 \(i\)的 \(x\) 序列之和，借此中间变量我们可以将不等式转化为：

这里的SPFA与原始的SPFA有所区别，在SPFA之前将所有节点加入队列，并且置dist为0，因为差分约束系统不保证图的连通性，所以需要事先建立一个虚拟节点作为源点，向所有边连接一条权值为0的有向边，以上的操作便是人工省略了虚拟源点的步骤。

SPFA实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<queue>
#include<cstring>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;

const int MAXN = 300 + 6;
const int MAXM = 2000 + 6;
int n, cur = 0;
int a[MAXN];
int head[MAXN];
int vis[MAXN], vis[MAXN], inq[MAXN], dist[MAXN];

//采用链式前向星的结构
struct Edge {
	int to;
	int next;
	int w;
}edge[MAXM];

void addEdge(int x, int y, int w) {
	edge[cur].to = y;
	edge[cur].next = head[x];
	edge[cur].w = w;
	head[x] = cur++;
}

void SPFA() {
	queue<int> qq;
	rep(i, 0, n + 1) {
		qq.push(i);
		vis[i] = 1;
		dist[i] = 0;
		inq[i] = 1;
	}
	while (!qq.empty()) {
		int x = qq.front();
		qq.pop();
		inq[x]++;	//x进队的次数，超过n遍证明有负环
		vis[x] = 0;
		if (inq[x] > n) {
			cout << "No answer" << endl;
			return;
		}
		for (int i = head[x]; i != -1; i = edge[i].next) {
			int nx = edge[i].to;
			if (dist[nx] < dist[x] + edge[i].w) {
				dist[nx] = dist[x] + edge[i].w;
				if (!vis[nx]) {		//如果没有拜访过
					vis[nx] = 1;
					qq.push(nx);
				}
			}
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(head, -1, sizeof(head));
	cin >> n;
	rep(i, 1, n + 1)  cin >> a[i];
	rep(i, 0, n - 2) {
		addEdge(i + 3, i, -(a[i + 2] * 3 + 2)); 
		addEdge(i, i + 3, a[i + 2] * 3);
	}
	addEdge(2, 0, -(a[1] * 2 + 1));		//对开头两个单独处理
	addEdge(0, 2, a[1] * 2);
	addEdge(n, n - 2, -(a[n] * 2 + 1)); //对结尾两个单独处理
	addEdge(n - 2, n, a[n] * 2);
	rep(i, 1, n + 1) 
		addEdge(i - 1, i, 1);	//每个数都要大于等于1
	SPFA();
	a[1] = dist[1];
	rep(i, 2, n + 1)  
		a[i] = dist[i] - dist[i - 1];
	cout << a[1];
	rep(i, 2, n + 1)  
		cout << ' ' << a[i];
	return 0;
}

关于main函数中ios::sync_with_stdio(false)的相关用法简介，可见 关于ios::sync_with_stdio(false)和cin.tie(nullptr)

思路（搜索+剪枝）

剪枝1

vis[][][]数组记录在到达第s个位置时（此时b[s],b[s-1]均已知），根据关系推知b[s+1] = 3*a[s]-b[s]-b[s-1]+i（因为题目给的是整数除法，其中 \(i \in (0 \cdots 2)\)，这样，当到达当前状态时（状态 : (s,b[s-1],b[s])），如果发现已经访问过了，说明这种状态不可能满足条件，否则程序已经找到满意的结果，可以直接输出了，这样可以直接剪枝掉之后的所有步骤，效率大大增加。

剪枝2

用flag标记 是否已经找到解，如果找到，之后的所有未完成的搜索，直接返回。

注意：第一个位置与最后的位置单独处理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<cstring>
#include<set>
#include<cmath>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<k;++i)
#define mst(a,b) memset((a),(b),sizeof(a))
#include<cstring>
using namespace std;
typedef long long LL;
typedef vector<int, int> pii;
const int MAXN = 305;
int n;
int a[MAXN];
int b[MAXN];
bool vis[MAXN][MAXN][MAXN];
bool flag;
void dfs(int s, int p1, int p2) {
	if (vis[s][p1][p2] || flag) return;
	vis[s][p1][p2] = true;
	if (s == n - 1) {
		rep(i, 0, 3) {//单独处理最后一个
			if ((b[n] = (3 * a[s] - p1 - p2 + i)) > 0 && (b[n - 1] + b[n]) / 2 == a[n]) {
				flag = true;
				rep(i, 1, n + 1) {
					printf("%d ", b[i]);
				}
				break;
			}
		}
		return;
	}
	rep(i, 0, 3) {
		b[s + 1] = 3 * a[s] - p1 - p2 + i;//递推下一个位置的b[s+1]
		if (b[s + 1] > 0) { // 可能有解
			dfs(s + 1, b[s], b[s + 1]);
		}
	}

}

int main() {
	scanf("%d", &n);
	rep(i, 1, n + 1) scanf("%d", &a[i]);
	rep(i, 1, 2 * a[1] + 1) {//最大只能是 2*a[1]
		b[1] = i; b[2] = a[1] * 2 - b[1];
		dfs(2, b[1], b[2]);
		b[1] = i; b[2] = a[1] * 2 - b[1] + 1;
		dfs(2, b[1], b[2]);
	}

	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2019-2024 鞠桥丹-QIAODAN JU
  • 访问人数: | 浏览次数:

请我喝杯蓝莓汁吧~

支付宝
微信