题目一：金币

1.题目来源：

NOIP2015 普及组 T1，难度红色，入门签到题。

2.题目描述：

3.题目解析：

问题转化：求下面的一个数组的前 k 项和。

4.算法原理：

模拟

签到题，只需要进行简单的模拟就可以了~~~

我们可以定义两个变量 cur 和 tmp

tmp 表示当前加的是哪一个数。

cnt 表示当前这个数还要加多少次。

仔细观察，可以发现，1加1次，2加2次，3加3次，……，n加n次。

每加一次某一个数，这个数对应的 cnt --，当 cnt 为 0 时，tmp++， cnt = tmp；

5.代码实现：

#include <iostream>using namespace std;int main()
{int k; cin >> k;int ret = 0;int tmp = 1; // 当前加的数是 1int cnt = 1; // 当前这个数还需要加 1 次 for(int i = 1; i <= k; i++){ret += tmp;cnt--;if(cnt == 0){tmp++;cnt = tmp;}}cout << ret << endl;return 0;
}

6.总结反思：

在算法竞赛中，签到题是一定要拿满分的，签到题要的是快准狠，竞赛时千万不能着急、慌张，想明白之后再写，遇到 bug 在草稿纸上仔细模拟，再说一遍，千万不要着急，越着急越错。

题目二：接水问题

1.题目来源：

NOIP2010普及组T2，难度橙色，签到题。

2.题目描述：

3.题目解析：

这道题，给了我一个深刻的教训 —— 一定要仔细读题！！！！！！

我在这道题卡了很长时间，刚开始没有看到初始接水顺序已经确定，以为可以自己安排。朝着贪心方向浪费了很多时间。

这道题其实就是一道简单的模拟题。直接按照题目模拟即可。

4.算法原理：

模拟+贪心，针对每一位学生，找出所有的水龙头中，最早结束的那一个，让他在那里接水。

对于贪心正确性可以用交换论证法来证明。这里是显然正确的，就不再赘述了。

可以用一个小根堆来模拟，先扔 m 个 0 进去，然后不断取出堆顶元素，修改后再扔进去。最终结果就是小根堆堆中的最大值。

时间复杂度：O（n log m）

当然了，本题用数组来模拟也是可以的，时间复杂的：O（n * m）

5.代码实现：

用小根堆来模拟：

#include <iostream>
#include <queue>
#include <vector>using namespace std;int n, m;int main()
{cin >> n >> m;// 小根堆 priority_queue<int, vector<int>, greater<int>> heap;for(int i = 1; i <= m; i++){heap.push(0);}int ret = 0;for(int i = 1; i <= n; i++){int x; cin >> x;int t = heap.top(); heap.pop();t += x;heap.push(t);ret = max(ret, t);}cout << ret << endl;return 0;
}

用数组来模拟：

#include <iostream>using namespace std;const int N = 110;int n, m;
int a[N]; // 存水龙头使用总时间信息 int main()
{cin >> n >> m;int ret = 0;for(int i = 1; i <= n; i++){int x; cin >> x;int mini = 0; // 要放入的水龙头的编号int d = 0x3f3f3f3f; // 最小值for(int j = 1; j <= m; j++){if(d > a[j]){d = a[j];mini = j;}} a[mini] += x;ret = max(ret, a[mini]);}cout << ret << endl;return 0;
}