devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

第十五届蓝桥杯C++ B组题解_蓝桥杯15届省赛题解

作者：我家自动化 | 2024-04-26 11:18:10

赞

踩

蓝桥杯15届省赛题解

 

A. 握手问题

填空题

        小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。在会议上， 大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进 行一次握手（且仅有一次）。但有 7 个人，这 7 人彼此之间没有进行握手（但 这 7 人与除这 7 人以外的所有人进行了握手）。请问这些人之间一共进行了多 少次握手？

        注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。

思路：

模拟

        将50个人从1到50标号，对于每两个人之间只握一次手，我们可以将问题转化为每个人只主动和标号比他大的人握一次手，那么标号为 1 的人，需要主动握 49 次，标号为 2 的人，需要主动握 48 次，以此类推，标号为 i 的人需要主动握 50 - i 次。（这边强烈建议 I 人往后排）

        经过上述流程，我们即可得到不加限制条件下的总握手次数为 1 + 2 + ... + 48 + 49 = 1225

        接下来我们来处理限制条件，我们假设相互之间没有握手的这七个人为标号 1 ~ 7 的七个人，那么如果他们之间有相互握手的话，根据前述流程可得他们之间握手次数为 1 + 2 + ... + 6  = 21

        用总次数减去多余握手次数（前七个人间相互握手次数）即得到限制条件下的握手次数，即为 1204

可用代码实现求和、求差过程

       

代码实现： 

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	int sum1 = 0, sum2 = 0;
  8. 	for(int i = 1; i <= 50; i ++)
  9. 	{
  10. 		sum1 += 50 - i;
  11. 	}
  12. 	
  13. 	for(int i = 1; i <= 7; i ++)
  14. 	{
  15. 		sum2 += 7 - i;
  16. 	}
  17. 	
  18. 	printf("%d", sum1 - sum2);
  19. 	return 0;
  20. }

 

B. 小球反弹

填空题

        有一长方形，长为 343720 单位长度，宽为 233333 单位长度。在其内部左 上角顶点有一小球（无视其体积），其初速度如图所示且保持运动速率不变，分 解到长宽两个方向上的速率之比为 dx : dy = 15 : 17。小球碰到长方形的边框时 会发生反弹，每次反弹的入射角与反射角相等，因此小球会改变方向且保持速 率不变（如果小球刚好射向角落，则按入射方向原路返回）。从小球出发到其第 一次回到左上角顶点这段时间里，小球运动的路程为多少单位长度？答案四舍 五入保留两位小数。

f607c65de1a84a7982df16f44f39c033.png

思路：

不会写，不知道答案是多少，不知道在哪找答案

代码实现：

//整个空框占个位置（实际没打算补）

C. 好数

编程题

         一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位 · · · ）上 的数字是奇数，偶数位（十位、千位、十万位 · · · ）上的数字是偶数，我们就称 之为“好数”。

        给定一个正整数 N，请计算从 1 到 N 一共有多少个好数。

 输入格式

 一个整数 N（1 ≤ N ≤ 1e7）

输出格式 

输出一个整数表示 1 到 N 之间好数的个数

样例输入1 

24

样例输出1 

7

样例输入2

2024

样例输出2 

150

 思路：

枚举 + 数位拆分

         对于 1 ~ N 中的每一个数字，我们都需要判断它是否是好数（依次判断每一位数字是否符合条件），于是我们需要对每一位数字进行数位拆分，因为 N 最大为 1e7，所以每个数字数位拆分的最大时间复杂度 lgN 小于10。依次枚举1 ~ N中每一个数字，对其进行数位拆分判断是否为好数，计数输出答案即可

代码实现：

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. bool check(int x)
  6. {
  7. 	int k = 1, w;
  8. 	while(x)
  9. 	{
  10. 		w = x % 10;
  11. 		if(k % 2 != w % 2) return false;
  12. 		
  13. 		x /= 10;
  14. 		k ++;
  15. 	}
  16. 	return true;
  17. }
  18.  
  19. int main()
  20. {
  21. 	int n, ans = 0;
  22. 	scanf("%d",&n);
  23. 	
  24. 	for(int i = 1; i <= n; i ++)
  25. 	{
  26. 		if(check(i))
  27. 		{
  28. 			ans ++;
  29. 		}
  30. 	}
  31. 	
  32. 	printf("%d", ans);
  33. 	return 0;
  34. }

 

D. R 格式 

编程题

        小蓝最近在研究一种浮点数的表示方法：R 格式。对于一个大于 0 的浮点数 d，可以用 R 格式的整数来表示。给定一个转换参数 n，将浮点数转换为 R 格式整数的做法是：

        1. 将浮点数乘以 2^n（2 的 n 次方） ;

        2. 四舍五入到最接近的整数。

输入格式 

一行输入一个整数 n 和一个浮点数 d，分别表示转换参数，和待转换的浮点数。

输出格式 

输出一行表示答案：d 用 R 格式表示出来的值。

 样例输入

2 3.14

样例输出 

13

思路：

高精度加法模拟

        用 string 读入浮点数 d，将其逆置之后，循环 n 次，每次循环使 d 加上它本身，最后四舍五入输出整数位即可（最初逆置过了，记得从后往前输出）

代码实现：

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int n;
  8. string s;
  9.  
  10. // s 自加 s 
  11. void Do()
  12. {
  13. 	int a, f = 0, m = s.size();
  14. 	for(int i = 0; i < m; i ++)
  15. 	{
  16. 		if(s[i] == '.') continue;
  17. 		a = f; f = 0;
  18. 		a += 2 * (s[i] - '0');
  19. 		
  20. 		if(a >= 10) f = 1;
  21. 		a %= 10;
  22. 		s[i] = '0' + a;
  23. 	}
  24. 	
  25. 	if(f) s += '1';
  26. } 
  27.  
  28. int main()
  29. {
  30. 	ios::sync_with_stdio(0);
  31. 	cin.tie(0); cout.tie(0);
  32. 	
  33. 	cin >> n >> s;
  34. 	reverse(s.begin(), s.end());
  35. 	
  36. 	//加倍 n 次 
  37. 	while(n --)
  38. 	{
  39. 		Do();
  40. 	}
  41. 	
  42. 	//四舍五入
  43. 	int a, m = 0, f = 0;
  44. 	while(s[m] != '.') m ++;
  45. 	
  46. 	if(s[m - 1] >= '5') f = 1; m ++;
  47. 	while(f && m < s.size())
  48. 	{
  49. 		s[m] += 1;
  50. 		f = 0;
  51. 		if(s[m] > '9')
  52. 		{
  53. 			s[m] = '0';
  54. 			f = 1;
  55. 		}
  56. 		
  57. 		m ++;
  58. 	}
  59. 	
  60. 	if(f) s += '1';
  61. 	
  62. 	//输出
  63. 	n = s.size() - 1;
  64. 	while(s[n] != '.')
  65. 	{
  66. 		cout << s[n --];
  67. 	}
  68. 	return 0;
  69. }

 

E.宝石组合

编程题

        在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有 着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗 宝石都有一个与生俱来的特殊能力，可以发出不同强度的闪光。小蓝共找到了 N 枚宝石，第 i 枚宝石的 “闪亮度” 属性值为 Hi，小蓝将会从这 N 枚宝石中选出三枚进行组合，组合之后的精美程度 S 可以用下图公式来衡量

ddecbc0d26ed4e0d8f702cef84e07903.png

        小蓝想要使得三枚宝石组合后的精美程度 S 尽可能的高，请你帮他找出精美程度最高的方案。如果存在多个方案 S 值相同，优先选择按照 H 值升序排列后字典序最小的方案。

 输入格式：

 第一行包含一个整数 N 表示宝石个数。

第二行包含 N 个整数表示 N 个宝石的 “闪亮度”。

输出格式： 

输出一行包含三个整数表示满足条件的三枚宝石的 “闪亮度”。

 样例输入：

5

1 2 3 4 9

样例输出： 

1 2 3

 思路：

约数 + 枚举

        打表可以发现精美程度 S 其实是三个宝石闪亮度的最大公约数（别问我怎么发现的，我也不知道，群友说的，我赛时纯暴力），当然，佬们也可以尝试用题给式子推导一下，本题解不再赘述（主要我也不会推导）

        我们用邻接表来存所有宝石闪亮度中，1 ~ 100000的倍数，st数组用于存放所有宝石闪亮度中1 ~ 100000之间每个数字的倍数出现的次数。从大到小去寻找第一个倍数出现3个或3个以上的数字，则这个数字就是所有宝石选择方案中能得到的最大的精美程度 S。

        此处注意我们将所有宝石闪亮度从大到小排序，优先去在邻接表中插入较大闪亮度（用头插法），以保证我们后面输出时按字典序（从小到大的顺序，我也好奇为什么蓝桥杯要整个字典序这个名词）去输出。

        注意：数组一定要开得足够大，因为邻接表中每个宝石的闪亮度会被存它的约数个数次，只开1e5是远远不够的

代码实现： 

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1e6 + 20;
  8. int n, q[N], st[N];
  9. int h[N], e[2 * N], ne[2 * N], idx;
  10.  
  11. bool cmp(int a, int b)
  12. {
  13. 	return a > b;
  14. }
  15.  
  16. void add(int x, int y)
  17. {
  18. 	e[idx] = y;
  19. 	ne[idx] = h[x];
  20. 	h[x] = idx ++;
  21. }
  22.  
  23. void check(int x)
  24. {
  25. 	for(int i = 1; i <= x / i; i ++)
  26. 	{
  27. 		if(x % i == 0)
  28. 		{
  29. 			add(i, x);
  30. 			
  31. 			st[i] ++;
  32. 			if(i != x / i)
  33. 			{
  34. 				st[x / i] ++;
  35. 				add(x / i, x);
  36. 			}
  37. 		}
  38. 	}
  39. }
  40.  
  41. int main()
  42. {
  43. 	scanf("%d",&n);
  44. 	for(int i = 1; i <= n; i ++)
  45. 	{
  46. 		scanf("%d",&q[i]);
  47. 	}
  48. 	
  49. 	sort(q + 1, q + n + 1, cmp);
  50. 	
  51. 	memset(h, -1, sizeof(h));
  52. 	for(int i = 1; i <= n; i ++)
  53. 	{
  54. 		check(q[i]);
  55. 	}
  56. 	
  57. 	int k = 1;
  58. 	for(int i = 100010; i > 1; i --)
  59. 	{
  60. 		if(st[i] >= 3)
  61. 		{
  62. 			k = i;
  63. 			break;
  64. 		}
  65. 	}
  66. 	
  67. 	for(int i = h[k], cnt = 0; cnt < 3; i = ne[i], cnt ++)
  68. 	{
  69. 		printf("%d ", e[i]);
  70. 	}
  71. 	
  72. 	return 0;
  73. }

 

F.数字接龙

编程题

        小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为 N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整 数。游戏规则如下：

        1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一 步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

        2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列 要满足：0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。

        3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

        4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再 从 (1, 0) 移动到 (0, 1) 线路就会交叉。

        为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图 2 所示；因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1 是一个迷宫示例，它所对应的答案就是：41255214。

688cb713bd6b4e29be00dadc448d8329.png

        现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出 字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

 输入格式：

第一行包含两个整数 N、K。

接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式： 

输出一行表示答案。如果存在答案输出路径，否则输出 −1。

样例输入： 

3 3

0 2 0

1 1 1

2 0 2

样例输出：

41255214

 思路：

DFS模拟

        我们从起点出发，以0 ~ 7 的顺序依次判断当前点的周围8个点是否符合题给要求（该点上的数字、路径是否交叉、该点是否被走过、是否越界），当搜到第一条路径时，直接全部返回（因为我们是按 0 ~ 7 的顺序去搜的，所以第一次找到的路径一定为字典序最小的路径）。这里采用 unordered_map去记录两点之间是否存在路径，进而判断路径是否交叉。

        注意：

                1. 从main函数进入dfs的时候，u的传值一定不要直接传1，因为k可能为1（血的教训）

                2.题面有歧义，当测试点为 1 1 0 （0为棋盘上的数字）时，要输出-1还是无输出不确定，赛时我写的没有输出，但是C语言网上按-1输出的，卡了好久才发现

代码实现： 

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. bool f;
  8. int n, k, q[20][20], st[20][20];
  9. vector<int> ans, w;
  10. unordered_map<long long, int> mp; //用于记录两点之间是否有连线
  11.  
  12. void dfs(int x, int y, int cnt, int u)
  13. {	
  14. 	if(f) return;
  15. 	if(cnt == n * n)
  16. 	{
  17. 		if(x == n && y == n)
  18. 		{
  19. 			f = 1;
  20. 			
  21. 			if(ans > w) ans = w;
  22. 			return;
  23. 		}
  24. 		return;
  25. 	}
  26. 	
  27. 	if(x == n && y == n)
  28. 	{
  29. 		return;
  30. 	}
  31. 	
  32. 	int a, b;
  33. 	for(int i = 0; i < 8; i ++)
  34. 	{
  35. 		switch(i)
  36. 		{
  37. 			case 0: a = x - 1; b = y; break;
  38. 			case 1: a = x - 1; b = y + 1; break;
  39. 			case 2:	a = x; b = y + 1; break;
  40. 			case 3: a = x + 1; b = y + 1; break;
  41. 			case 4: a = x + 1; b = y; break;
  42. 			case 5: a = x + 1; b = y - 1; break;
  43. 			case 6: a = x; b = y - 1; break;
  44. 			case 7: a = x - 1; b = y - 1; break;
  45. 		}
  46. 		
  47. 		if(i == 1)
  48. 		{
  49. 			if(mp[((x - 1) * 1000 + y) * 10000000 + x * 1000 + (y + 1)])
  50. 			{
  51. 				continue;
  52. 			}
  53. 		}
  54. 		else if(i == 3)
  55. 		{
  56. 			if(mp[((x + 1) * 1000 + y) * 10000000 + x * 1000 + (y + 1)])
  57. 			{
  58. 				continue;
  59. 			}
  60. 		}
  61. 		else if(i == 5)
  62. 		{
  63. 			if(mp[((x + 1) * 1000 + y) * 10000000 + x * 1000 + (y - 1)])
  64. 			{
  65. 				continue;
  66. 			}
  67. 		}
  68. 		else if(i == 7)
  69. 		{
  70. 			if(mp[((x - 1) * 1000 + y) * 10000000 + x * 1000 + (y - 1)])
  71. 			{
  72. 				continue;
  73. 			}
  74. 		}
  75. 		
  76. 		if(a > 0 && a <= n && b > 0 && b <= n && q[a][b] == u && !st[a][b])
  77. 		{
  78. 			if(i % 2)	
  79. 			{
  80. 				mp[(a * 1000 + b) * 10000000 + x * 1000 + y] = 1;
  81. 				mp[(x * 1000 + y) * 10000000 + a * 1000 + b] = 1;
  82. 			}
  83. 			st[a][b] = 1;
  84. 			
  85. 			w[cnt] = i;
  86. 			
  87. 			dfs(a, b, cnt + 1, (u + 1) % k);
  88. 			
  89. 			st[a][b] = 0;
  90. 			if(i % 2)
  91. 			{
  92. 				mp[(a * 1000 + b) * 10000000 + x * 1000 + y] = 0;
  93. 				mp[(x * 1000 + y) * 10000000 + a * 1000 + b] = 0;
  94. 			}
  95. 			
  96. 			if(f) return;
  97. 		}
  98. 	}
  99. }
  100.  
  101. int main()
  102. {
  103. 	scanf("%d %d",&n, &k);
  104. 	for(int i = 1; i <= n; i ++)
  105. 	{
  106. 		for(int j = 1; j <= n; j ++)
  107. 		{
  108. 			scanf("%d",&q[i][j]);
  109. 			ans.push_back(10);
  110. 			w.push_back(0);
  111. 		}
  112. 	}
  113. 	
  114. 	if(n == 1 || q[1][1] != 0)
  115. 	{
  116. 		printf("-1");
  117. 		return 0;
  118. 	}
  119. 	
  120. 	st[1][1] = 1;
  121. 	dfs(1, 1, 1, 1 % k);
  122.  
  123. 	if(f)
  124. 	{
  125. 		for(int i = 1; i < n * n; i ++)
  126. 		{
  127. 			printf("%d", ans[i]);
  128. 		}
  129. 	}
  130. 	else printf("-1");
  131. 	return 0;
  132. }

G.爬山

编程题

        小明这天在参加公司团建，团建项目是爬山。在 x 轴上从左到右一共有 n座山，第 i 座山的高度为 hi。他们需要从左到右依次爬过所有的山，需要花费的体力值为 S = Σni=1hi。

        然而小明偷偷学了魔法，可以降低一些山的高度。他掌握两种魔法，第一种魔法可以将高度为 H 的山的高度变为 ⌊√H⌋，可以使用 P 次；第二种魔法可以将高度为 H 的山的高度变为 ⌊H/2⌋，可以使用 Q 次。并且对于每座山可以按任意顺序多次释放这两种魔法。

        小明想合理规划在哪些山使用魔法，使得爬山花费的体力值最少。请问最优情况下需要花费的体力值是多少？

 输入格式：

输入共两行。

第一行为三个整数 n，P，Q。

第二行为 n 个整数 h1，h2，. . . ，hn。

输出格式： 

输出共一行，一个整数代表答案。

样例输入：

4 1 1

4 5 6 49

样例输出：

18

思路： 

贪心

        先声明一下：贪心做法是我在赛时的写法，同时也是蓝桥官方直播时给出的做法，但在4月13日 13:08被群友以 2 1 1 48 49的测试用例hack了，所以本题解提供的属于是错误思路（博主太菜了，想不出正解，见谅），诸君图一乐即可，若有所思所启，荣幸之至，绝无误人子弟之意。

        较片面地看来，我们只需每次对当前最高的山使用魔法使其变矮，使用完所有魔法得到的便是最优结果，而在使用魔法时，要优先使用能使当前最高山变得更矮的魔法，故使用大根堆来存储所有山的高度，每次弹出堆顶，对其进行操作（若有两种魔法，则二选其优，否则有哪个用哪个），最后将所有的山高度求和即可，时间复杂度O（nlogn）。

 代码实现：

  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. int n, x, y;
  8. priority_queue<int> q;
  9.  
  10. long long a, b, ans;
  11.  
  12. int main()
  13. {
  14. 	scanf("%d %d %d",&n, &x, &y);
  15. 	for(int i = 1; i <= n; i ++)
  16. 	{
  17. 		scanf("%lld",&a);
  18. 		q.push(a);
  19. 	}
  20. 	
  21. 	while(x || y)
  22. 	{
  23. 		long long t = q.top();
  24. 		q.pop();
  25. 		a = t / 2, b = sqrt(t);
  26. 		
  27. 		if(x && y)
  28. 		{
  29. 			if(a < b)
  30. 			{
  31. 				y --;
  32. 				q.push(a);
  33. 			}
  34. 			else
  35. 			{
  36. 				x --;
  37. 				q.push(b);
  38. 			}
  39. 			
  40. 		}
  41. 		else if(x)
  42. 		{
  43. 			x --;
  44. 			q.push(b);
  45. 		}
  46. 		else
  47. 		{
  48. 			y --;
  49. 			q.push(a);
  50. 		}
  51. 	}
  52. 	
  53. 	while(!q.empty())
  54. 	{
  55. 		ans += q.top();
  56. 		q.pop();
  57. 	}
  58. 	
  59. 	printf("%lld", ans);
  60. }

 

H.拔河

编程题

        小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。

        为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续:{ al1, al1+1, ..., ar1−1, ar1 } 和 { al2, al2+1, ..., ar2−1, ar2 }，其中 l1 ≤ r1 < l2 ≤ r2。

        两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输入格式： 

输入共两行。

第一行为一个正整数 n。

第二行为 n 个正整数 ai。

输出格式： 

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

样例输入：

5
10 9 8 12 14

 样例输出： 

1 

 思路：

枚举 + 二分 感谢学长 @福建易烊万玺 的顶级理解思路，让本蒟蒻在有生之年还能将这道题写出来

        因为两支队伍均要求连续，我们可以将用前缀和预处理以缩短求连续区间和的时间。事先将所有可能的区间存入multiset容器中，枚举 l1 和 r1，在每一个 r1 被枚举到时，将multiset容器中所有以当前 r1 为左端点的区间全部删掉，则容器中剩余的区间即为所有可能的第二队的区间，随后枚举 l1 ，用multiset内置的二分函数lower_bound去找到第一个大于等于 当前枚举区间力量值的值，令其与当前枚举区间力量值相减，得到的结果与当前答案比较取较小值，再取容器中最大的不大于前枚举区间力量值的值，相减后与当前答案取最小值，枚举结束即可得到最小可能差值。（由于本人较菜，描述可能有些难以消化，建议结合代码理解，若还是理解不了，请移步参考文章）

 代码实现：

  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 1010;
  8. int n;
  9. long long ans = 1e9, q[N];
  10. multiset<long long> s; 
  11.  
  12. int main()
  13. {
  14. 	scanf("%d",&n);
  15. 	for(int i = 1; i <= n; i ++)
  16. 	{
  17. 		scanf("%lld",&q[i]);
  18. 		q[i] += q[i - 1];
  19. 	}
  20. 	
  21. 	for(int i = 1; i <= n; i ++)
  22. 	{
  23. 		for(int j = i; j <= n; j ++)
  24. 		{
  25. 			s.insert(q[j] - q[i - 1]);
  26. 		}
  27. 	}
  28. 	
  29. 	int res;
  30. 	for(int r1 = 1; r1 <= n; r1 ++)
  31. 	{
  32. 		for(int r2 = r1; r2 <= n; r2 ++)
  33. 		{
  34. 			auto k = s.find(q[r2] - q[r1 - 1]);
  35. 			s.erase(k);
  36. 		}
  37. 		
  38. 		for(int l1 = 1; l1 <= r1; l1 ++)
  39. 		{
  40. 			auto k = s.lower_bound(q[r1] - q[l1 - 1]);
  41. 			if(k != s.end())
  42. 			{
  43. 				ans = min(ans, abs(*k - q[r1] + q[l1 - 1]));
  44. 			}
  45. 			if(k != s.begin())
  46. 			{
  47. 				k --;
  48. 				ans = min(ans, abs(*k - q[r1] + q[l1 - 1]));
  49. 			}
  50. 		}
  51. 	}
  52. 	
  53. 	printf("%lld", ans);
  54. 	return 0;
  55. }

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/490641
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号