当前位置：首页 > java >正文

2025年3月电子学会等级考试五级题——4、收费站在哪里

java 2025/7/4 23:29:32

文章目录

- 题目
- 代码
- 公式
- 小结

题目

4、收费站在哪里
在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0=x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集了一大堆过路费发票后，我们筛选出了 n(n-1)/2 个距离的值，现在想知道收费站都分布在哪里？
当然对应一组距离值，可能有多组解，你只要输出任何一个即可。
时间限制：1000
内存限制：65536
输入
输入第一行给出正整数 m（< 50），即距离值的数量。随后一行给出 m 个距离，均为 int 范围内的正整数。
输出
按坐标值升序列出所有收费站的位置，其中 x1=0。同行数字间以 1 个空格分隔，行首尾不得有多余空格。注：题目保证所有坐标为 int 范围内的非负整数。
样例输入
10
3 4 6 8 1 3 5 2 4 2
样例输出
0 2 4 5 8

代码

#include <bits/stdc++.h>
using namespace std;
int n,//收费站数 m,//距离数量 maxd,//d;
vector<int> sta;//向量容器（动态数组）存放收费站 
multiset<int,greater<int>> dis;//可以重复元素，自动排序的关联容器，用来存放收费站间距离 
//共num个数，从x开始，dis是剩余的距离，sta是认定的收费站 
void view(string s,multiset<int,greater<int>>& dis,vector<int>& sta){cout<<s<<endl;cout<<"所剩距离：\n";for(auto i=dis.begin();i!=dis.end();i++)cout<<*i<<"\t";cout<<endl;cout<<"已有站点：\n";for(auto i=sta.begin();i!=sta.end();i++)cout<<*i<<"\t";cout<<endl;
}
//递归，深搜，找到n-2个合格收费站
//4个参数，分别是：1已明确收费站数，2已经明确的距离（往后要找小于等于的）
//3关联容器，存放剩余的距离； 4向量容器，已经明确的收费站 
bool go(int num,int x,multiset<int,greater<int>> dis,vector<int>& sta){cout<<"收费站数"<<num<<"\t需要"<<n<<endl;view("出发",dis,sta);if(num==n){//目标：凑够n个收费站cout<<"ok!!!!!!!!!!!!!!!!!\n";return 1;}//比x(上个)小的剩余距离作为站点，开始尝试 for(multiset<int,greater<int>>::iterator i=dis.lower_bound(x);i!=dis.end();i++){cout<<"剩余距离："<<*i<<"\t";multiset<int,greater<int>> disb=dis;//拷贝剩余距离 bool k=1;//先设定该距离可以作为收费站 for(vector<int>::iterator j=sta.begin();j!=sta.end();j++){//遍历已有收费站 cout<<"到站点"<<*j<<"的距离"<<abs(*j-*i);//判定该收费站和已有收费站的间距都存在 if(disb.find(abs(*j-*i))==disb.end()){k=0;cout<<"没有\n";break;} else cout<<"有\n"<<endl; }//如果间距都有，剔除这些间距 if(k){for(vector<int>::iterator j=sta.begin();j!=sta.end();j++)disb.erase(disb.find(abs(*j-*i)));//清除该收费站产生的距离 sta.push_back(*i);//多了个收费站 //sort(sta.begin(),sta.end());view("搞定一个",disb,sta);if(go(num+1,*i,disb,sta))return 1;//递归 sta.pop_back();//回溯 }else cout<<"该收费站不存在!\n";}cout<<"失败!\n";return 0;
}
int main(){freopen("data.cpp","r",stdin);cin>>m;//共几个距离 for(int i=1;i<=m;i++){cin>>d;dis.insert(d);//收费站间距放进关联容器，能自动排序 maxd=max(d,maxd);//得到最大距离 }n=(1+sqrt(1+8*m))/2;//n(n-1)/2=m,推出一元二次方程n^2-n-2*m=0;得到解 sta.push_back(0),sta.push_back(maxd);//可以明确0和最大距离始末两个收费站，放进vector sort(sta.begin(),sta.end());multiset<int,greater<int>>::iterator x=dis.find(maxd);dis.erase(x);//已经明确最大距离是最后一个收费站，剔除间距集合 view("开始",dis,sta);if(go(2,maxd,dis,sta)){//递归，深搜，找到合格的n-2个收费站 sort(sta.begin(),sta.end());//升序输出所有收费站 for(auto i=sta.begin();i!=sta.end();i++)cout<<*i<<" ";}return 0;
}