Codeforces 389A Fox and Number Game(贪心)

题意:给出一个序列X,能进行如下操作,选择两个下i, j(i != j), 将Xi的值减去Xj, 求怎么样操作能使的最后序列和最小.

思路:做法是每次都找序列里最大的和次大的,最大的减掉次大的,如果都变成了相同的大小,就退出循环.

#include <cstdio>
#include <algorithm>
#include <numeric>
using namespace std;
const int MAX = 101;

int X[MAX];

int main(int argc, char const *argv[]){
	int n, ans = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &X[i]);
	}
	while(true){
		int mp = max_element(X, X + n) - X;
		int smp = mp, smv = 0;
		for(int i = 0; i < n; ++i){
			if(X[i] < X[mp] && smv < X[i]){
				smv = X[i];
				smp = i;
			}
		}
		if(mp == smp)break;
		X[mp] -= X[smp];
	}

	printf("%d\n", accumulate(X, X + n, 0));
	return 0;
}

Codeforces 389A Fox and Number Game(贪心),布布扣,bubuko.com

Codeforces 389A Fox and Number Game(贪心)

原文：http://blog.csdn.net/zxjcarrot/article/details/23094639