C++ 贪心算法

理解贪心算法

• 贪心算法采用的是贪心策略
• 在每一步中都采取最优解（局部最优解），以期望得到最终的全局最优解

例子

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main(){
	int a[510] = {0}; // 表示每个人的打水时间的数组
	int r, n, s = 0; // 水龙头数r，人数n，总时间s
	cin >> n >> r;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a+1, a+n+1); // 排序，将装水时间最小的排在前面
	// 从r+1个人开始，需要加上排队排队时间
	for(int i = 1; i <= n; i++){
		if(i >= r+1){
			a[i] = a[i] + a[i-r]; // 计算第r+1个人及其之后所有人的打水时间
		}
		s = s + a[i];
	}
	cout << s;
}