第十四届蓝桥杯省赛C++ C组——三国游戏（贪心算法）

题目来源：4965. 三国游戏 - AcWing题库

题目 3158: 蓝桥杯2023年第十四届省赛真题-三国游戏 - C语言网 (dotcpp.com)

时间限制: 3s 内存限制: 320MB 

题目描述

小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i 个事件发生时会分别让 X, Y, Z 增加Ai , Bi ,Ci 。

当游戏结束时 (所有事件的发生与否已经确定)，如果 X, Y, Z 的其中一个大于另外两个之和，我们认为其获胜。例如，当 X > Y + Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?

如果不存在任何能让某国获胜的情况，请输出 −1 。

输入格式

输入的第一行包含一个整数 n 。

第二行包含 n 个整数表示 Ai，相邻整数之间使用一个空格分隔。

第三行包含 n 个整数表示 Bi，相邻整数之间使用一个空格分隔。

第四行包含 n 个整数表示 Ci，相邻整数之间使用一个空格分隔。

输出格式

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

样例输入

3
1 2 2
2 3 2
1 0 7

样例输出

2

提示

发生两个事件时，有两种不同的情况会出现获胜方。

发生 1, 2 事件时蜀国获胜。

发生 1, 3 事件时吴国获胜。

对于 40% 的评测用例，n ≤ 500 ；

对于 70% 的评测用例，n ≤ 5000 ；

对于所有评测用例，1 ≤ n ≤ 105，1 ≤ Ai , Bi ,Ci ≤ 109 。

 我的初始代码（DFS暴力枚举）：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
 
int n;
int max_ans=-1;
int step;
int x,y,z;
 
int k;
void dfs(int u,vector<vector<int>> &a){
	if(u==n+1){
		k++;
		//对选择的情况做出判断，符合就保留该情况的步数，不符合就跳过
		if(!(x+y<z||x+z<y||y+z<x))
			return;//step是全局变量，不能在此处修改，后续递归要恢复现场
			//step=-1;//或者将step设为递归函数的参数，变为局部变量
		//最后结果一定得是保存最大的，必须迭代保存
		max_ans=max(max_ans,step);
		return ;
	}
	else{
		//第u件发生：根
		x+=a[0][u-1];
		y+=a[1][u-1];
		z+=a[2][u-1];
		step++;//不同组合事件发生数
		//下一件事件分类：左
		dfs(u+1,a);
		//第一种情况触底出来后，恢复现场，进行另一个选择
		x-=a[0][u-1];
		y-=a[1][u-1];
		z-=a[2][u-1];
		step--;
		//另一个选择就是不加
		//下一件事情分类：右
		dfs(u+1,a);
	}
}
 
int main()
{
	cin>>n;
	vector<vector<int>> a(3,vector<int>(n,0));
	for(int i=0;i<3;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	
	dfs(1,a);//从第一件事情开始，步数初始值为0
	
	cout<<max_ans;
	return 0;
}
/*
  10
  7 8 10 7 10 9 4 4 8 7
  3 7 8 7 5 3 9 6 6 1
  1 8 7 7 7 5 5 4 1 9
 */

传参版：step ：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
 
int n;
int max_ans=-1;
//int step;
int x,y,z;
 
int k;
void dfs(int u,vector<vector<int>> &a,int step){
	if(u==n+1){
		k++;
		//对选择的情况做出判断，符合就保留该情况的步数，不符合就跳过
		if(!(x+y<z||x+z<y||y+z<x))
			//return;//step是全局变量，不能在此处修改，后续递归要恢复现场
			step=-1;//或者将step设为递归函数的参数，变为局部变量
			//最后结果一定得是保存最大的，必须迭代保存
		max_ans=max(max_ans,step);
		return ;
	}
	else{
		//第u件发生：根
		x+=a[0][u-1];
		y+=a[1][u-1];
		z+=a[2][u-1];
		step++;//不同组合事件发生数
		//下一件事件分类：左
		dfs(u+1,a,step);
		//第一种情况触底出来后，恢复现场，进行另一个选择
		x-=a[0][u-1];
		y-=a[1][u-1];
		z-=a[2][u-1];
		step--;
		//另一个选择就是不加
		//下一件事情分类：右
		dfs(u+1,a,step);
	}
}
 
int main()
{
	cin>>n;
	vector<vector<int>> a(3,vector<int>(n,0));
	for(int i=0;i<3;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	
	dfs(1,a,0);//从第一件事情开始，步数初始值为0
	
	cout<<max_ans;
	return 0;
}
/*
  10
  7 8 10 7 10 9 4 4 8 7
  3 7 8 7 5 3 9 6 6 1
  1 8 7 7 7 5 5 4 1 9
 */

最后当然是超时了，www……4965. 三国游戏 - AcWing题库

代码运行状态： 错误数据如下所示   ×
输入
100000
8 10 1 8 1 1 1 6 8 1 8 7 9 7 4 7 10 3 2 7 3 2 3 9 8 5 9 1 7 9 3 3 6 10 5 2 5 4 10 7 2 1 8 2 5 3 2 6 9 4 2 8 1 3 4 9 4 3 9 9 6 6 10 10 6 1 2 3 3 2 1 6 2 3 1 3 3 10 7 7 9 10 2 5 1 7 4 4 2 4 9 2 8 2 10 5 1 4 3 8 3 8 5 7 6 4 5 3 9 1 2 3 9 10 8 8 6 10 8 4 8 2 4 2 1 5 5 2 9 4 3 9 8 1 6 8 8 4 5 5 1 3 5 3 5 8 2 6 6 8 3 9 3 1 5 1 4 1 6 10 3 7 3 5 3 4 8 1 10 9 1 3 8 10 3 3 8 3 3 5 5 1 6 2 2 1 7 1 4 2 9 8 8 7 5 3 6 6 1 7 2 3 9 10 1 6 3 9 10 5 8 3 6 9 9 4 3 8 10 1 2 8 2 2 5 8 9 1 9 1 1 6 5 7 5 2 4 1 10 4 9 2 6 8 8 10 1 10 3 10 3 4 8 10 10 2 7 10 1 1 7 2 7 4 7 10 3 6 6 3 10 7 1 1 2 9 9 7 7 1 7 6 6 7 9 4 9 5 3 8 3 7 10 1 9 7 1 6 5 1 10 9 4 2 5 8 3 1 9 8 5 6 5 5 8 1 10 10 9 1 3 5 6 8 3 3 7 5 6 1 2 2 3 1 3 10 4 10 10 6 3 2 4 10 3 8 1 5 7 1 3 1 6 6 6 9 6 3 3 7 10 3 8 3 8 9 7 1 5 8 4 6 8 7 9 2 3 1 10 8 3 10 2 7 2 8 5 9 9 2 7 2 4 5 6 1 1 4 2 10 9 6 5 4 2 10 1 4 8 8 6 6 7 9 6 3 9 10 7 4 8 9 9 3 4 2 7 3 3 9 5 8 3 9 9 6 5 2 9 7 8 10 5 7 4 1 1 5 10 3 9 8 3 3 10 5 5 6 10 6 3 1 7 1 4 9 3 3 10 2 1 6 1 4 2 3 7 1 5 5 10 9 8 4 9 3 2 4 7 8 3 8 7 1 4 6 1 9 10 1 1 9 8 1 3 1 6 2 7 7 2 4 2 10 10 1 5 2 7 2 2 7 10 7 7 1 6 9 8 2 8 7 1 7 3 3 4 3 2 10 7 10 4 6 6 4 6 1 5 8 8 7 2 3 8 7 2 5 9 5 3 2 8 10 5 3 2 10 6 10 9 4 1 1 10 5 2 9 7 9 5 8 7 10 4 1 7 3 10 5 3 5 6 10 3 2 5 5 2 5 8 1 8 10 7 3 3 7 5 7 10 6 5 3 3 1 1 6 8 9 1 1 10 2 9 10 2 8 6 3 7 7 4 2 5 5 1 10 1 3 2 4 4 6 3 9 7 4 9 4 9 5 7 10 7 9 4 4 2 10 2 4 4 10 1 9 10 4 2 9 4 5 1 6 4 4 10 5 6 10 7 9 9 8 3 9 5 3 9 10 5 8 9 3 6 4 2 6 1 4 7 10 8 1 7 8 4 10 6 3 1 10 4 10 3 8 10 3 3 10 7 7 10 10 10 3 7 6 2 5 3 7 7 2 2 8 7 3 6 4 1 8 10 9 3 4 3 4 1 10 10 5 4 9 3 6 10 2 3 10 9 10 8 5 7 6 5 3 8 3 7 10 8 7 6 4 7 9 6 2 5 1 2 5 6 6 8 10 2 6 5 1 4 8 4 6 3 8 5 6 9 7 1 2 6 5 2 7 6 3 4 10 7 5 1 6 7 8 6 2 8 2 2 10 6 9 1 10 2 10 2 6 5 10 9 9 10 4 5 9 4 1 7 2 3 10 2 7 2 7 1 4 3 10 5 9 4 1 8 2 8 6 2 2 1 10 10 8 2 6 7 1 9 1 6 3 6 4 10 1 3 7 5 6 1 1 7 5 4 1 2 8 8 10 4 1 4 10 10 3 2 5 7 4 2 5 10 9 2 3 8 8 1 2 7 5 9 3 6 5 7 9 5 5 1 5 5 9 1 3 10 2 6 3 7 4 5 6 8 7 2 1 1 ...
 
输出
标准答案
33410

 佬的码（先膜拜为敬）：第十四届蓝桥杯C组题目 三国游戏_算法_m0_74163986-GitCode 开源社区 (csdn.net)

#include<bits/stdc++.h>
using namespace std;
int n;
int ans = 0;
int s[100010];
int a[100010], b[100010], c[100010];
void check(int *a1, int *b1, int *c1) {
	for (int i = 1; i <= n; i++) s[i] = a1[i] - b1[i] - c1[i];
	sort(s + 1, s + 1 + n);
	long long sum = 0;
	int cnt = 0;
	for (int i = n; i >= 1; i--) {
		sum += s[i];
		if (sum <= 0) {
			break;
		}
		cnt++;
	}
	//	cout << cnt << endl;
	ans = max(ans, cnt);
	
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] ;
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i] ;
	}
	for (int i = 1; i <= n; i++) {
		cin >> c[i] ;
	}
	check(a, b, c);
	check(b, a, c);
	check(c, b, a);
	
	cout << (ans == 0 ? -1 : ans);
	
}

膜拜后我的贪心初始码（调试的快乐谁能懂……）：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
/*
  题目分析：每发生一件事件，会对各国兵力都造成影响，题目的目的
  是使得一方国家兵力超出剩余两国之和，可用数学中的“作差法”将问题转化
  ——使得一国兵力差距远拉其余两国，盯着的值就是X-Y-Z或其他组合
  而题给的每件事都会对这个差值造成影响，我们采用“动态过程分析法”
  初始的差距是0，随着每一事件的发生，都会对这个差值产生影响，这是可计算的
  对应相减即可。题目是要给出最多发生几件事，而没有要求事件发生的顺序
  和具体是哪件事，故可将这些事件的影响按从小到大顺序排好，看看最多能发生
  几件事使得差距X-Y-Z一直处于大于0的状态，输出次数即可
  而有三种获胜情况，故可写一个函数，三次调用即可
 */
 
int check(vector<int> a,vector<int> b,vector<int> c){
	vector<int> dis(a.size(),0);
	int sum=0;//初始兵力差距：a-b-c==0
	for(int i=0;i<a.size();i++){
		dis[i]=a[i]-b[i]-c[i];//事件发生对差距的影响，正数利于差距大于0，负数使得差距缩小
	}
	sort(dis.rbegin(),dis.rend());//每次都从最大的开始加，尽可能多的发生事件，贪心思想
	int cnt=0;
	for(int i=0;i<dis.size();i++){
		sum+=dis[i];
		if(sum<=0){//sum需要大于0
			break;//符合条件才可继续向右走
		}
		cnt++;
	}
	if(cnt==0)
		cnt=-1;
	return cnt;
}
 
int main()
{
	int n;
	cin>>n;
	vector<vector<int>> a(3,vector<int>(n,0));
	for(int i=0;i<3;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	int num1=check(a[0],a[1],a[2]);
	int num2=check(a[1],a[2],a[0]);
	int num3=check(a[2],a[0],a[1]);
	int cnt=max(num1,max(num2,num3));
	printf("%d",cnt);
	return 0;
}

终于能过之后……，忽略数据范围，sum累加要爆int了，赶紧换 long long

代码运行状态： 错误数据如下所示   
输入
100000
519678117 947068443 241792522 939161520 644564420 399454701 352554069 729936048 429708867 806220700 475142410 773942310 807595476 536574487 534007289 408081034 846960511 393672602 295362262 169000160 320483834 725075369 421437198 786502330 957699838 406180673 499429575 801281538 347251371 42868147 913795913 263276010 70336161 332798323 334674344 688076706 223942559 738154708 678743064 610634600 613490700 950108670 131334064 511494804 233837489 385719138 511096914 817051870 637753225 533942176 713876746 638667574 141513833 752597137 509819443 261175320 982752412 817017909 134467838 943940817 36535015 323133075 924343297 467266606 971249792 288903754 910439049 294595622 713618860 491511309 658409732 344418043 633081675 833124994 289951287 177524776 21947389 522471002 116769025 759766857 454651529 606777441 114911173 950433603 318098792 261902156 683868516 403166653 171296491 87936360 488778221 742088973 185059698 489370954 878994309 299540004 135467525 122363121 859757243 570241193 383222309 154732545 452281047 431671415 783803509 395765216 897108632 268645234 514889787 841616504 696596035 87690484 402076955 229888829 326736432 22473721 888793111 83786000 487359729 805709695 535951609 264754880 769159223 222477742 321020341 42530341 840656598 932094045 865074654 45249030 436424587 769113408 932497012 893194594 864736848 352957808 323229226 626943738 152400723 556317653 966051818 83224976 94172742 873590507 384142824 820256960 733756543 308565617 483874646 600107003 13328965 609493542 576942200 159033186 998278758 279295087 572437047 478862686 279288583 12796589 321500089 221742549 692210569 615221357 875659122 617373687 754635103 790991735 941038207 219530599 82436758 180037563 469932723 444852206 11615774 788542200 137968763 428238642 196220541 240312556 175999880 70507759 210422936 693614751 978731390 712949755 28178964 601906045 498590325 564823264 303300672 703292603 776030742 395856192 184377683 182961466 452909302 355675862 728188749 741327763 80229231...
 
输出
2
标准答案
39171

改后AC码 ：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
/*
  题目分析：每发生一件事件，会对各国兵力都造成影响，题目的目的
  是使得一方国家兵力超出剩余两国之和，可用数学中的“作差法”将问题转化
  ——使得一国兵力差距远拉其余两国，盯着的值就是X-Y-Z或其他组合
  而题给的每件事都会对这个差值造成影响，我们采用“动态过程分析法”
  初始的差距是0，随着每一事件的发生，都会对这个差值产生影响，这是可计算的
  对应相减即可。题目是要给出最多发生几件事，而没有要求事件发生的顺序
  和具体是哪件事，故可将这些事件的影响按从小到大顺序排好，看看最多能发生
  几件事使得差距X-Y-Z一直处于大于0的状态，输出次数即可
  而有三种获胜情况，故可写一个函数，三次调用即可
 */
 
int check(vector<int> a,vector<int> b,vector<int> c){
	vector<int> dis(a.size(),0);
	long long sum=0;//初始兵力差距：a-b-c==0，做多有10^9列,每列的差距如果为10^9
//那sum将高达10^18，int(10^9)/long long(10^19)
	for(int i=0;i<a.size();i++){
		dis[i]=a[i]-b[i]-c[i];//事件发生对差距的影响，正数利于差距大于0，负数使得差距缩小
	}
	sort(dis.rbegin(),dis.rend());//每次都从最大的开始加，尽可能多的发生事件，贪心思想
	int cnt=0;
	for(int i=0;i<dis.size();i++){
		sum+=dis[i];
		if(sum<=0){//sum需要大于0
			break;//符合条件才可继续向右走
		}
		cnt++;
	}
	if(cnt==0)
		cnt=-1;
	return cnt;
}
 
int main()
{
	int n;
	cin>>n;
	vector<vector<int>> a(3,vector<int>(n,0));
	for(int i=0;i<3;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	int num1=check(a[0],a[1],a[2]);
	int num2=check(a[1],a[2],a[0]);
	int num3=check(a[2],a[0],a[1]);
	int cnt=max(num1,max(num2,num3));
	printf("%d",cnt);
	return 0;
}

小小贪心，看我不一点点的拿捏你……（未完待续）

书接上文，在看到二分支枚举马上就用最笨的方法，直接用dfs暴搜，然后超时，可想而知，dfs这种暴力方式，在面对数据规模很大的时候是会超时的，而关于数据规模和算法的联系，笔记里也有，应注意多复习。

闲言少叙，解决算法题，可以利用数学思维来将问题转化，这是非常聪明的做法，算法题本来就应该这么做。而不是无脑的去暴力枚举，毫无思维技巧性可言。
本题使用了”做差法“、”动态过程分析法“。

所谓的思维技巧，都是想让解决问题的方法更快速，更全面。

以后解题，要避免上来就无脑爆搜，这是下下策，应该用数学的眼光去看待一切算法问题。