贪心-取数游戏c
目录
[贪心] 取数游戏(c++)
今天给大家讲取数游戏这道题
题目:给出2×n个自然数。游戏双方分别为A方（计算机）和B方（对弈的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，取得的数字总和最大者为胜方；双方和相等，属于A胜。试问A方可否有必胜的策略？
输入格式:第1行：1个整数n(1<=n<=100) 第2行：2×n个整数（每个数<30000），相邻两个数之间用空格分开
输出格式 第1行：2个整数，分别为A方取得的数之和与B方取得的数之和。
样例输入
2
1 2 3 4
样例输出
6 4
这道题是个典型的贪心算法
思路就是他一共有偶数个数字也就是说你要么从头取数要么从结尾取数 那么如果从头取数他取到的就是奇数位上的数字 反之如果是从结尾取则取得的就是偶数位上的数字 也就是说我们只需要求出奇数位上的数字大还是偶数位上的数字大就行了
那么讲完思路就上代码
#include<iostream>
using namespace std;
int main(){
int a,sum=0,num=0,b[100005];
cin>>a;
for(int i=1;i<=a*2;i++){
cin>>b[i];//输入
}
for(int i=1;i<=a*2;i++){
if(i%2==0){//判断奇偶
sum+=b[i];
}
else{
num+=b[i];
}
}
if(sum>=num){//看那个先输出
cout<<sum<<" "<<num;
}
else{
cout<<num<<" "<<sum;
}
}