本文涉及的基础知识点
本博文代码打包下载
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−1j=0∑n−1d(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++**实现。
