自动搬运

查看原文

来自洛谷，原作者为

	Im_Klee 你是来找可莉玩的吗？|| 蹦蹦炸弹！

搬运于2025-08-24 22:58:30，当前版本为作者最后更新于2024-10-02 21:37:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

帮帮可莉吧！让可莉通过审核吧！

题意

给定 $n$ 个数，求最少的等差数列个数，恰好覆盖 $n$ 个数各一次。

至少 $2$ 项，数值在 $0$ 到 $59$ 之间。

允许有重复的等差数列。

$X$ 等差数列必须按规律在 $[0,59]$ 之间出现。

分析：

1. 考虑到 DFS 超时，而答案在 $17$ 以内，尝试 IDDFS。
2. 预处理可能的等差数列，使得等差数列的每一项都在输入中出现。
3. 维护 check 函数检查第 $i$ 个等差数列的每一项是否都有出现，设找到 $cnt$ 条。
4. 将等差数列按项数从多到少排序，贪心选取，从而使得需要的公交路线最少。
5. 维护 $cnt_i$ 表示时间点 $i$ 出现的车的数量。

代码：

#include<bits/stdc++.h>
using namespace std。
const int maxn = 305。
int cnt, dep, n, s[65]。

struct node
{
	int x, d, num。
	bool operator < (const node &a) const
	{
		return num > a.num。
	}
}route[3600]。

	
bool check(int x, int d)
{
	for(int i = x。 i < 60。 i += d)
		if(s[i] == 0)
			return false。
	return true。
}

bool dfs(int cur, int k, int sum) //cur 层次，k线路， sum已经覆盖的车的数量 
{
	if(cur == dep)
		return sum == n。
	if(sum + (dep-cur) * route[k].num < n) //可行性剪枝 
		return false。
	for(int i = k。 i <= cnt。 i++)
	{
		if(check(route[i].x, route[i].d) == true)
		{
			for(int j = route[i].x。 j < 60。 j += route[i].d)
				s[j]--。
			if(dfs(cur+1, i, sum + route[i].num) == true) //第i条路线还可以选!! 
				return true。
			for(int j = route[i].x。 j < 60。 j += route[i].d) //回溯 
				s[j]++。
		}
	}
	return false。
}

int main()
{
	cin >> n。 //n车 
	for(int i = 1。 i <= n。 i++)
	{
		int x。
		cin >> x。 //时间 
		s[x]++。 //计数器 
	}
	for(int i = 0。 i < 60。 i++) //首项 
	{
		for(int d = i + 1。 i + d < 60。 d++) //公差 
		{
			if(check(i, d) == true) //找到可行的线路 
			{
				cnt++。
				route[cnt].x = i。 //首项 
				route[cnt].d = d。 //公差 
				route[cnt].num = (59-i) / d + 1。 //覆盖的公交车数量 
			}
		}
	}
	sort(route + 1, route + cnt + 1)。 //按照覆盖的公交车数量从大到小排序 
	dep = 0。
	while(dfs(0, 1, 0) == false) //当前的深度，选择线路编号， 覆盖的总公交 
		dep++。
	cout << dep。
	return 0。
}
//注意这组数据 0  4  4  8 8 12 12 ……