解决历史遗留问题.jpg
[APIO/CTSC2007]数据备份
显然，选的一定是相邻的两个城市。 所以问题转化成，给一个差分数组，选 \(k\) 个不相邻的数，使得和最小。
这就是经典的种树的问题。
我们每次贪心的选最大值，然后把左右两边的全删掉，并再插入 \(a[pre[i]]+a[nxt[i]]-a[i]\)，这样再选到它的时候意味着选两边的，不选中间的，而且再左右的也不选。这样重复 \(K\) 次即可。
CF730I
这个诡异的数据范围应该是留给费用流的。
就是源点连向各个学生，费用为 \(0\)，流量为 \(1\)，每个学生连向两个点，分别代表两个社团，流量为 \(1\)，费用为负的权值，然后这两个点再连向汇点，流量分别为 \(p,s\)。
首先我们将 \(a_i\) 值最大的 \(p\) 个人选出来，然后考虑选出另外一个社团的人。假设我们选的是还没有加入任何社团的人，那就直接选 \(b_i\) 最大的就行。 否则我们从编程社团选一个人到体育社团，然后从无业游民里选一个到编程社团，那贡献就是 \(b_i-a_i+a_j\)，那就再开两个堆表示 \(b_i-a_i\)，和 \(a_j\) ，然后直接做就行。注意判重，\(a_i\) 和 \(b_i\) 的堆需要记录不是任何社团的，而 \(b_i-a_i\) 的不需要管，因为一定是编程社团的。
[NOI2017] 蔬菜
不说这题的反悔贪心的做法（我觉得没有这种有意思还不好写）.
就说有一个弱化版的题 UVA316 Supermarket
就是有一个神仙的想法就是先按价值排序，然后加入到消失点前里消失点最近的位置。这样能保证尽可能的多放物品，如果加不进去，就说明这个物品没啥用，直接扔了就行。
这题也是一样，对于每种蔬菜在大根堆里，先插入 \(a_i+s_i\),然后取出最大的，也是放到可行的尽可能后的位置，如果不存在这样的位置，这种蔬菜就直接扔掉就好啦（所以保证复杂度），然后如果这种蔬菜还能放，就在堆里插入 \(a_i\)。
询问的时候就直接问插入 \(x\times m\) 个蔬菜时的价值和即可。我们刚才考虑的是最坏情况，也就是对每种蔬菜尽可能往后放，这样的目的是让别的蔬菜能放进去。而询问的时候前面就是有 \(x\times m\) 个空位，原来那些蔬菜是放在后面的，现在全部堆到前面也不成问题，所以不用在意时间的问题。
标签：反悔,然后,插入,社团,蔬菜,贪心 From： https://www.cnblogs.com/cc0000/p/16942839.html