A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，
但各自的实力都不足以吞下对方，经过谈判后，
双方同意用一个公平的方式来处理这片金矿。
处理的规则如下：
他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。


马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?

（两伙马贼均会采取对己方有利的策略）

/*
A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，
但各自的实力都不足以吞下对方，经过谈判后，
双方同意用一个公平的方式来处理这片金矿。
处理的规则如下：
他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。

马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?
（两伙马贼均会采取对己方有利的策略）
*/ 
#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;

vector<int>count(int m, vector<int>nums) {
	int sumA = 0, sumB = 0, flag = 0, temp=0;
	vector<int>answer;
	for (int i = 0; i < m - 1; i += 2) {
		//上次存的索引位置为偶数
		if (flag % 2 == 0) {
			//此时不需要换
			if (sumA + nums[i] >= sumB + nums[i + 1]) {
				sumA += nums[i];
				sumB += nums[i + 1];
			}
			//此时要换
			else if (sumA + nums[i] < sumB + nums[i + 1]) {
				temp = sumA;
				sumA = sumB;
				sumB = temp;
				sumA += nums[i + 1];
				sumB += nums[i];
				flag = i + 1;
			}
		}
		//上次存的索引位置为奇数
		else if (flag % 2 != 0) {
			//此时无需更换
			if (sumA + nums[i + 1] >= sumB + nums[i]) {
				sumA += nums[i + 1];
				sumB += nums[i];
			}
			//此时需要更换
			else if (sumA + nums[i + 1] < sumB + nums[i]) {
				temp = sumA;
				sumA = sumB;
				sumB = temp;
				sumA += nums[i];
				sumB += nums[i + 1];
				flag = i;
			}
		}
	}
	answer.push_back(sumA);
	answer.push_back(sumB);
	return  answer;
}

int main()
{
	cout << "请输入测试组数" << endl;
	int n = 0, m = 0, temp=0;
	vector<int>nums,answer;
	cin >> n;
	while (n) {
		cout << "请输入每组数据的元素个数" << endl;
		cin >> m;
		cout << "请输入每个元素的值" << endl;
		for (int i = 0; i < m; i++) {
			cin >> temp;
			nums.push_back(temp);
		}
		cout << "元素输入完毕" << endl;
		//调用函数
		answer=count(m, nums);
		cout << "马贼A获得的钱币数:" << answer[0]<< endl;
		cout << "马贼B获得的钱币数:" << answer[1] << endl;
		//输出个换行，为了美观
		cout << endl;
		n--;
		nums.clear();
	}
    return 0;
}