算法每日一题7

2023-04-11

竞赛 / 算法 / 每日一题

Word count: 2.4k | Reading time≈ 11 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、随机数据下的最短路问题

lanqiao-1366：随机数据下的最短路问题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：图论、SPFA算法

$\textcolor{red}{分析：}$

（1）起点s入队，计算它所有邻居到s的最短距离。把s出队，状态有更新的邻居入队，没更新的不入队。

（2）现在队列的头部是s的一个邻居u。弹出u，更新它所有邻居的状态，把其中有状态变化的邻居入队列。

（3）继续以上过程，直到队列空。这也意味着，所有结点的状态都不再更新。最后的状态就是到起点s的最短路径。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 随机数据下的最短路问题
using ll = long long;
const int N = 5e3+10;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

struct edge{
	int to;// 目标点(终点) 
	ll w;// 权重 
	edge(int tt, ll ww){
		to = tt;
		w = ww;
	}
};

int n, m, s;
vector<edge>eg[N];
int inq[N];// 标记点i在队列中
ll dist[N];

void spfa(int s){// s为起点 
	memset(dist, 0x3f, sizeof(dist));// 0x3f等价于INF
	dist[s] = 0;// 起点到自己的距离是0
	queue<int>q;
	q.push(s);// 从s开始，s进队列
	inq[s] = 1;// s在队列中 
	while(!q.empty()){
		int u = q.front();
		q.pop();
		inq[u] = 0;// u不在队列中 
		if(dist[u]==INF)continue;
		for(int i=0;i<eg[u].size();++i){// 遍历邻居结点 
			int v = eg[u][i].to;
			ll w = eg[u][i].w;
			if(dist[v]>dist[u]+w){// u的第i个邻居v，它借道u，到s更近
				dist[v] = dist[u]+w;// 更新邻居v到s的距离
				if(!inq[v]){// 邻居v更新状态了，但v不在队列中，放进队列
					q.push(v);
					inq[v] = 1;
				}
			}
		}
	}
}

int main() {
	cin>>n>>m>>s;
	int a, b;ll c;
	for(int i=1;i<=m;++i){
		cin>>a>>b>>c;// a就是起点，v就是终点 
		eg[a].push_back(edge(b, c));
	}
	spfa(s);
	for(int i=1;i<=n;++i){// 点从1~n 
		if(dist[i]==INF)cout<<-1<<" ";
		else cout<<dist[i]<<" "; 
	}
	return 0;
}

2、聪明的猴子

lanqiao-862：聪明的猴子 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：图论、Kruskal算法、并查集、MST（最小生成树）

$\textcolor{red}{分析：}$

对边进行排序。
判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是kruskal算法的绝配。
以下代码能够通过示例数据，但是不能AC？？？

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 聪明的猴子——Kruskal算法与并查集得到最小生成树 
const int N = 5e3+10;
const int NN = 1e6+10;
struct edge{
	int u, v;// 起点与终点 
	double w;// 两点之间的距离 
}; 

edge eg[N];
int monkey[NN], x[N], y[N];// 分别为猴子的跳跃能力、树的x坐标与y坐标(方便求两树之间的距离w) 
int parent[N];// 存储结点的父节点，并查集
int m, n; // 猴子的个数、树的棵树 

bool comp(edge a, edge b){// 根据w升序排序 
	return a.w<b.w;
}

// 并查集
int find(int x){// 查找根节点 
	if(x!=parent[x]){
		parent[x] = find(parent[x]);
	}
	return parent[x];
} 

void merge(int x, int y){// 合并集合——连接x与y的根节点 
	int xx = find(x);
	int yy = find(y);
	if(xx!=yy)parent[yy] = xx;// yy为新的根节点 
}

int main() {
	cin>>m;
	for(int i=1;i<=m;++i)cin>>monkey[i];
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x[i]>>y[i];
	}
	// 构建图结构
	int cnt = 0;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j){// 避免重复计算距离 
			double w = sqrt(pow((x[i]-x[j]), 2)+pow((y[i]-y[j]), 2));// 计算距离
			eg[++cnt] = {i, j, w};// 初始化边数组 
		} 
	} 
	sort(eg+1, eg+1+cnt, comp);// 按照边权重升序排序 
	// 计算最小生成树以及MST中的最大边权重 
	for(int i=1;i<=n;++i){
		parent[i] = i;// 初始化根节点为本身 
	}
	int num = 0;// 存储最小生成树中结点的个数 
	double maxE = 0.0;// 存储MST中边权重的最大值 
	for(int i=1;i<=cnt;++i){// 遍历所有的边edge 
		if(find(eg[i].u)!=find(eg[i].v)){// 两个结点不具有相同的根节点 
			merge(eg[i].u, eg[i].v);// 合并
			num++;// 结点数量增加
			maxE = maxE>=eg[i].w?maxE:eg[i].w;// 更新MST中边的最大权重 
		}
		if(num==n-1)break;// n个结点组成MST之后只有n-1条边 
	} 
	int ans = 0;
	for(int i=1;i<=m;++i){
		if(monkey[i]>=maxE)ans++;// 满足要求的猴子数量+1 
	} 
	cout<<ans;
	return 0;
}

3、统计数字

lanqiao-535：统计数字 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：排序进阶

$\textcolor{red}{分析：}$

突出map容器的使用，合理利用map容器的性质；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 统计数字 
using ll = long long;
map<ll, int>h;//存储(自然数，个数) 
int n;

int main() {
	cin>>n;
	ll tmp;
	for(int i=0;i<n;++i){
		cin>>tmp;
		h[tmp]++;// 计算相同自然数的个数，map自动根据key进行升序排序 
	}
	for(auto &e:h){
		cout<<e.first<<" "<<e.second<<endl;
	}
	return 0;
}

4、错误票据

lanqiao-205：错误票据 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：排序进阶

$\textcolor{red}{分析：}$

很简单，根据题意直接计算即可；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 错误票据
const int N = 1e4+10;
int a[N];
int n;
int cnt = 0;
int ans1, ans2;

int main() {
	cin>>n;
//	while(scanf("%d", &a[cnt])!=EOF)cnt++;
	while(cin>>a[cnt])cnt++;
	sort(a, a+cnt);// 升序排序
	// 查找断号与重号
	for(int i=1;i<cnt;++i){
		if(a[i]-a[i-1]>1)ans1 = a[i-1]+1;
		else if(a[i]==a[i-1])ans2 = a[i];
	} 
	cout<<ans1<<" "<<ans2;
	return 0;
}

5、奖学金

lanqiao-531：奖学金 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：排序进阶

$\textcolor{red}{分析：}$

主要是排序规则的自定义；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 奖学金
struct stu{
	int id;// 学号 
	int sum;
	int Chinese;// 语文 
	bool operator < (const stu&a)const{// 重载<号，sort排序基于的就是< 
		if(sum==a.sum){
			if(Chinese==a.Chinese){
				return id<a.id;
			}
			return Chinese>a.Chinese;
		}
		return sum>a.sum;
	}
};
stu stu[310];
int n;

int main() {
	cin>>n;
	int x, y, z;
	for(int i=1;i<=n;++i){
		cin>>x>>y>>z;
		stu[i] = {i, (x+y+z), x};
	}
	sort(stu+1, stu+1+n); // 按照规则排序 
	for(int i=1;i<=5;++i){// 输出前5名 
		cout<<stu[i].id<<" "<<stu[i].sum<<endl;
	}
	return 0;
}

6、排列序数

lanqiao-269：排列序数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：枚举、排列

$\textcolor{red}{分析：}$

next_permutation的使用；

解决代码：

#include<bits/stdc++.h>
using namespace std;
string str, tmp;
int cnt = 0;

int main() {
	cin>>str;
	tmp = str;// tmp存储目标排列 
	sort(str.begin(), str.end());// 先得到最初的排列 
	while(tmp!=str){
		next_permutation(str.begin(), str.end());
		cnt++;
	}
	cout<<cnt;
	return 0;
}

7、付账问题

lanqiao-174：付账问题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：枚举、排列

$\textcolor{red}{分析：}$

贪心法：
1. 准备贪心：先将花费数组从小到大排序
2. 贪心策略：
  - 从数组最小的元素开始，每次做判断
  - 若当前元素小于剩余花费平均值，则取该元素不改变值，将平均成本转嫁到后续元素上
  - 若当前元素大于等于剩余花费平均值，则后续元素也大于该平均值，能够承接前较小元素的成本，将当前元素之后的所有元素取剩余花费平均值
3. 结束贪心，解出标准差
精确度：

本题对于精确度要求较高，总结如下提升准确度的方法：
1. long long提升整数的准确度
2. double可以承接18位左右有效数字
3. 尽量减少除法，转换成乘法
4. 尽量减少会导致误差的计算的次数

解决代码：

#include<bits/stdc++.h>
using namespace std;
//  付账问题——尽量避免使用除法导致误差累积(转为使用乘法)
const int N = 5e5+10;
using ll = long long;
ll a[N];
int n;
ll S;


int main() {
	cin>>n>>S;
	for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1, a+1+n);// 升序排序 
	double sum = 0;// 方差
	double avg = 1.0*S/n;// 总平均值
	// 贪心算法开始 
	for(int i=1;i<=n;++i){
		if(a[i]*(n-i+1)<S){// 第i个人的钱不能够达到还差金额S与剩下人数(n-i+1)的平均值 
			sum += (a[i]-avg)*(a[i]-avg);
			S -= a[i];// 更新还差金额 
		}else{// 第i个人的钱能达到剩下平均值,证明后面的人都可以不用付完自己的全部钱了 
			double cur_avg = 1.0*S/(n-i+1);// 每人只需要付还差的金额S分摊到余下人身上的平均值那么多钱即可
			sum += (cur_avg-avg)*(cur_avg-avg)*(n-i+1); 
			break;
		}
	}
	printf("%.4f", sqrt(sum/n));
	return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.