【二分查找 图论】P8794 [蓝桥杯 2022 国 A] 环境治理|普及

devtools/2025/2/28 11:10:28/

本文涉及的基础知识点

本博文代码打包下载
C++二分查找
C++图论

[蓝桥杯 2022 国 A] 环境治理

题目描述

LQ 国拥有 n n n 个城市，从 0 0 0 到 n − 1 n - 1 n−1 编号，这 n n n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D D D，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 P P P 来衡量 LQ 国的出行环境， P P P 定义为：

P = ∑ i = 0 n − 1 ∑ j = 0 n − 1 d ( i , j ) P=\sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} d(i,j) P=i=0∑n−1​j=0∑n−1​d(i,j)

其中 d ( i , j ) d(i,j) d(i,j) 表示城市 i i i 到城市 j j j 之间灰尘度最小的路线对应的灰尘度的值。

为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1 1 1，但每条道路都有一个灰尘度的下限值 L L L，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。

具体的计划是这样的：

  • 第 1 1 1 天， 0 0 0 号城市对与其直接相连的道路环境进行改善；
  • 第 2 2 2 天， 1 1 1 号城市对与其直接相连的道路环境进行改善；

……

  • 第 n n n 天， n − 1 n - 1 n−1 号城市对与其直接相连的道路环境进行改善；
  • 第 n + 1 n + 1 n+1 天， 0 0 0 号城市对与其直接相连的道路环境进行改善；
  • 第 n + 2 n + 2 n+2 天， 1 1 1 号城市对与其直接相连的道路环境进行改善；

……

LQ 国想要使得 P P P 指标满足 P ≤ Q P \leq Q P≤Q。请问最少要经过多少天之后， P P P 指标可以满足 P ≤ Q P \leq Q P≤Q。如果在初始时就已经满足条件，则输出 0 0 0；如果永远不可能满足，则输出 − 1 -1 −1。

输入格式

输入的第一行包含两个整数 n , Q n, Q n,Q，用一个空格分隔，分别表示城市个数和期望达到的 P P P 指标。

接下来 n n n 行，每行包含 n n n 个整数，相邻两个整数之间用一个空格分隔，其中第 i i i 行第 j j j 列的值 D i , j ( D i , j = D j , i , D i , i = 0 ) D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0) Di,j​(Di,j​=Dj,i​,Di,i​=0) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度。

接下来 n n n 行，每行包含 n n n 个整数，相邻两个整数之间用一个空格分隔，其中第 i i i 行第 j j j 列的值 L i , j ( L i , j = L j , i , L i , i = 0 ) L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0) Li,j​(Li,j​=Lj,i​,Li,i​=0) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度的下限值。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

样例输出 #1

2

提示

【样例说明】

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 3 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3 d(0,0)=0,d(0,1)=2,d(0,2)=3；
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 1 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1 d(1,0)=2,d(1,1)=0,d(1,2)=1；
  • d ( 2 , 0 ) = 3 , d ( 2 , 1 ) = 1 , d ( 2 , 2 ) = 0 d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0 d(2,0)=3,d(2,1)=1,d(2,2)=0。

初始时的 P P P 指标为 ( 2 + 3 + 1 ) × 2 = 12 (2 + 3 + 1) \times 2 = 12 (2+3+1)×2=12，不满足 P ≤ Q = 10 P \leq Q = 10 P≤Q=10;

第一天， 0 0 0 号城市进行道路改善，改善后的图示如下：

注意到边 ( 0 , 2 ) (0, 2) (0,2) 的值减小了 1 1 1，但 ( 0 , 1 ) (0, 1) (0,1) 并没有减小，因为 L 0 , 1 = 2 L_{0,1} = 2 L0,1​=2 ，所以 ( 0 , 1 ) (0, 1) (0,1) 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 3 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3 d(0,0)=0,d(0,1)=2,d(0,2)=3，
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 1 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1 d(1,0)=2,d(1,1)=0,d(1,2)=1，
  • d ( 2 , 0 ) = 3 , d ( 2 , 1 ) = 1 , d ( 2 , 2 ) = 0 d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0 d(2,0)=3,d(2,1)=1,d(2,2)=0。

此时 P P P 仍为 12 12 12。

第二天，1 号城市进行道路改善，改善后的图示如下：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

  • d ( 0 , 0 ) = 0 , d ( 0 , 1 ) = 2 , d ( 0 , 2 ) = 2 d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2 d(0,0)=0,d(0,1)=2,d(0,2)=2，
  • d ( 1 , 0 ) = 2 , d ( 1 , 1 ) = 0 , d ( 1 , 2 ) = 0 d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0 d(1,0)=2,d(1,1)=0,d(1,2)=0，
  • d ( 2 , 0 ) = 2 , d ( 2 , 1 ) = 0 , d ( 2 , 2 ) = 0 d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0 d(2,0)=2,d(2,1)=0,d(2,2)=0。

此时的 P P P 指标为 ( 2 + 2 ) × 2 = 8 < Q (2 + 2) \times 2 = 8 < Q (2+2)×2=8<Q，此时已经满足条件。

所以答案是 2 2 2。

【评测用例规模与约定】

  • 对于 30 % 30\% 30% 的评测用例， 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10， 0 ≤ L i , j ≤ D i , j ≤ 10 0 \leq L_{i,j} \leq D_{i,j} \leq 10 0≤Li,j​≤Di,j​≤10；
  • 对于 60 % 60\% 60% 的评测用例， 1 ≤ n ≤ 50 1 \leq n \leq 50 1≤n≤50， 0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L_{i,j} \leq D_{i,j} \leq 10^5 0≤Li,j​≤Di,j​≤105；
  • 对于所有评测用例， 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100， 0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L_{i,j} \leq D_{i,j} \leq 10^5 0≤Li,j​≤Di,j​≤105， 0 ≤ Q ≤ 2 31 − 1 0 \leq Q \leq 2^{31} - 1 0≤Q≤231−1。

蓝桥杯 2022 国赛 A 组 F 题。

二分查找+多源最短路

Check(mid)，多源最短路计算最短路(int)，再计算其和sum(long long)。返回sum <= Q。
二分类型：寻找首端。
参数返回：[0,107]
如果Check(ans)不成立，返回-1。
cur[i][j]记录mid后城市i到城市j之间的灰尘度。
max(mat[i][j]-mid/N*2-(i<mid%N)-(j<mid%N),L[i][j])

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>#include <bitset>
using namespace std;template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {vector<T> ret(n);for(int i=0;i<n;i++) {scanf(pFormat, &ret[i]);	}return ret;
}template<class T = int>
vector<T> Read( const char* pFormat = "%d") {int n;scanf("%d", &n);vector<T> ret;T d;while (n--) {scanf(pFormat, &d);ret.emplace_back(d);}return ret;
}string ReadChar(int n) {string str;char ch;while (n--) {do{scanf("%c", &ch);} while (('\n' == ch));str += ch;}return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {cin >> pr.first >> pr.second;
}template<class T = int >
class CFloyd
{
public:CFloyd(int n, const T INF = 1000 * 1000 * 1000) :m_INF(INF){m_vMat.assign(n, vector<T>(n, m_INF));for (int i = 0; i < n; i++) {m_vMat[i][i] = 0;}}void SetEdge(int i1, int i2, const T& dis, bool bDirect = false){m_vMat[i1][i2] = min(m_vMat[i1][i2], dis);if (!bDirect) {m_vMat[i2][i1] = m_vMat[i1][i2];}}vector<vector<T>> Dis(){auto vResMat = m_vMat;const int n = m_vMat.size();for (int i = 0; i < n; i++){//通过i中转for (int i1 = 0; i1 < n; i1++){if (m_INF == vResMat[i1][i]){continue;}for (int i2 = 0; i2 < n; i2++){//此时：m_vMat[i1][i2] 表示通过[0,i)中转的最短距离vResMat[i1][i2] = min(vResMat[i1][i2], vResMat[i1][i] + vResMat[i][i2]);//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离}}}return vResMat;};vector<vector<T>> m_vMat;//结果串const T m_INF;
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist(_Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd(_Pr pr){INDEX_TYPE leftInclude = m_iMin;INDEX_TYPE right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {
public:int Ans(vector<vector<int>>& mat, vector<vector<int>>& L, int Q) {const int N = mat.size();auto Check = [&](int mid) {auto cur = L;for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {cur[i][j] = max(cur[i][j], mat[i][j] - mid / N * 2 - (i < mid% N) - (j < mid% N));}CFloyd<int> floyd(N);floyd.m_vMat.swap(cur);auto res = floyd.Dis();long long ans = 0;for (const auto& v : res) {ans += accumulate(v.begin(), v.end(), 0);}return ans <= Q;};auto ans = CBinarySearch<int>(0, 1e7).FindFrist(Check);return Check(ans) ? ans : -1;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint N,Q;	cin >> N >> Q;vector < vector<int>> mat(N), L(N);for (int i = 0; i < N; i++) {mat[i] = Read<int>(N);}for (int i = 0; i < N; i++) {L[i] = Read<int>(N);}auto res = Solution().Ans(mat, L, Q);cout << res << std::endl;
#ifdef _DEBUG			Out(mat, "mat=");Out(L, "L=");printf(",Q=%d;", Q);
#endif			return 0;
}

单元测试

vector<vector<int>> mat, L;int Q;TEST_METHOD(TestMethod11){mat = { {0,2,4},{2,0,1},{4,1,0} }, L = { {0,2,2},{2,0,0},{2,0,0} }, Q = 10;auto res = Solution().Ans(mat, L, Q);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。


http://www.ppmy.cn/devtools/163330.html

相关文章

GitHub SSH连接问题解决指南

GitHub SSH连接问题解决指南

&#x1f50d; GitHub SSH连接问题解决指南 问题描述 遇到错误&#xff1a;ssh: connect to host github.com port 22: Connection refused 说明您的网络环境无法访问GitHub的SSH端口22&#xff0c;常见原因&#xff1a; 防火墙/网络运营商限制&#xff08;国内常见&#xf…
阅读更多...
1.2.2 使用Maven方式构建Spring Boot项目

1.2.2 使用Maven方式构建Spring Boot项目

本次实战通过Maven方式构建了一个Spring Boot项目&#xff0c;实现了简单的Web应用。首先&#xff0c;创建了Maven项目并设置好项目名称、位置、构建系统和JDK等。接着&#xff0c;添加了Spring Boot的父项目依赖和web、thymeleaf起步依赖。然后&#xff0c;创建了项目启动类He…
阅读更多...
腾讯SQL面试题解析：如何找出连续5天涨幅超过5%的股票

腾讯SQL面试题解析：如何找出连续5天涨幅超过5%的股票

腾讯SQL面试题解析：如何找出连续5天涨幅超过5%的股票 作者：某七年数据开发工程师 | 2025年02月23日 关键词：SQL窗口函数、连续问题、股票分析、腾讯面试题 一、问题背景与难点拆解 在股票量化分析场景中，"连续N天满足条件"是高频面试题类型。本题要求在单表stoc…
阅读更多...
【数据结构】二叉树（门槛极低的系统理解）

【数据结构】二叉树（门槛极低的系统理解）

本篇文章将进行图文讲述该种数据结构&#xff01;看完一定不会让你失望&#xff0c;好的文章不需要过多的浮夸&#xff0c;质量就是深得人心的砝码&#xff01;下面我总结了最形象的趣味理解方法&#xff0c;一遍看完终身不忘&#xff01;制作不易&#xff0c;能否一键三连呢&a…
阅读更多...
ODE卷-可以处理的最大任务数（200分)

ODE卷-可以处理的最大任务数（200分)

专栏订阅🔗 -> 赠送OJ在线评测 HWOD-E卷(101-120)-(200分)107.可以处理的最大任务数 可以处理的最大任务数 问题描述 LYA 是一家公司的项目经理，她需要安排公司的多个项目任务。每个任务都有一个开始时间和结束时间。LYA 希望在给定的时间范围内安排尽可能多的任务。 …
阅读更多...
AWS跨账号服务全解析：安全共享资源的最佳实践

AWS跨账号服务全解析：安全共享资源的最佳实践

在复杂的云环境中，企业常常需要将不同业务部门、项目或环境分配到独立的AWS账户中，以实现资源隔离和权限管控。然而，跨账户的资源共享与协作需求也随之而来。AWS为此提供了丰富的跨账号服务，允许不同账户之间安全、高效地共享资源。本文将深入解析这些服务，并结合实际场景…
阅读更多...
springBoot统一响应类型3.1版本

springBoot统一响应类型3.1版本

前言&#xff1a; 通过实践而发现真理&#xff0c;又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识&#xff0c;又从理性认识而能动地指导革命实践&#xff0c;改造主观世界和客观世界。实践、认识、再实践、再认识&#xff0c;这种形式&#xff0c;循环往…
阅读更多...
STM32微控制器为何不适合运行Linux系统的分析

STM32微控制器为何不适合运行Linux系统的分析

STM32微控制器不适合运行Linux系统的原因可以从多个角度进行分析。首先&#xff0c;STM32属于ARM Cortex-M系列的微控制器&#xff0c;这类微控制器主要设计用于实时操作、低功耗应用、以及成本敏感型应用场景。相比之下&#xff0c;Linux系统需要较高的计算能力和资源&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023