贪心-个人总结

i207M · 2018-09-01 23:28:02 · 个人记录

裸的贪心是不会考的，贪心的一个方法是：固定顺序，按照某种顺序，先考虑容易决定的

对于O(N(logN))的贪心，大部分是对数组进行排序或预处理后，！枚举！每个数字，求出对应的最优解更新答案，比直接构造出答案的数量要多；

P2279 [HNOI2003]消防局的设立

我们从深到浅考虑节点，当一个点没有被覆盖我们可以选择覆盖 他自己/父亲/爷爷/兄弟，而覆盖爷爷可以覆盖最多的点，所以应该贪心的覆盖爷爷；

DP的方法：

DP[i][0] 表示 选 i 为消防局
DP[i][1] 表示 {至少} 选了 i 的一个儿子为消防局
DP[i][2] 表示 {至少} 选了 i 的一个孙子为消防局
==================================以上三种状态是 i {一定被消防局覆盖} 的情况
state = 3, 4 :
DP[i][3] 表示 i 的 {所有} 儿子节点一定被消防局覆盖
DP[i][4] 表示 i 的 {所有} 孙子节点一定被消防局覆盖
==================================以上两种状态是 i {不一定被消防局覆盖} 的情况

环形均分纸牌--中位数问题

三种常见的区间贪心

一、线段覆盖

n个开区间(ai,bi)，选择尽量多个区间，使得这些区间两两不相交

按右端点升序排列，每次选择能选择的点中，右端点最小的；

二、区间选点

n个闭区间[ai,bi]，选择尽量少的点，使得每个区间至少有一个点

法一：

按右端点排序，每次选择可选区间的最后一个点；

法二：

按左端点排序，维护最后放置的位置；

当某个区间的右端点>lst，肯定要新放置一个，位置在r；

当某个区间的左端点<=lst，但右端点r<lst，lst应减小到r，以覆盖这个区间，同时，之前覆盖的区间都是可以覆盖的；

        double lst = -1e10;
        int ans = 0;
        for(ri i = 1; i <= n; ++i)
            if(p[i].l > lst)
            {
                ++ans;
                lst = p[i].r;
            }
            else lst = min(p[i].r, lst);

三、区间覆盖

数轴上有n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定的线段[s,t]

左端点升序排序，每次选择从当前起点能覆盖到的最长的区间；

POJ 1456

给定N个商品，每个商品有利润p和过期时间d，每天只能卖一个商品，过期商品不能再卖，求最大利润；

贪心策略：

在最优解中，对于每个时间t，应该在不卖出过期商品的前提下，尽量卖出利润前t大的商品；

按过期时间排序，扫描每个商品，建立一个小根堆

1.如果当前天数==堆的大小，如果它的利润大于堆顶，替换堆顶；

2.如果当前天数<堆的大小，直接插入；

贪心策略2：

每天都只能卖一种商品，所以一定是在能卖出的情况下，卖出利润最大的；

按利润排序，并查集维护时间，每个商品都在能卖的最后一天卖；

[NOI2014]随机数生成器

小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 N 行第 M 列的格子。

小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 N + M - 1 的升序序列，我们称之为路径序列。

小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？

我们需要贪心的做，然而我并没有想出来

我们要先到1，再到2（如果可以的话）...

每选择一个数，影响其实是修改了每一行的可行区间；

选择(x,y)，对于1 \rightarrow x-1，可行右端点缩小为y；对于x + 1 \rightarrow n，可行左端点增加为y；

画图一下；

    s = n + m - 1;
    for(ri i = 1; i <= s; ++i)
    {
        do
        {
            ++k;
            x = (bel[k] - 1) / m + 1, y = (bel[k] - 1) % m + 1;
        }
        while(y < l[x] || y > r[x]);
        printf("%d ", k);
        for(ri j = 1; j < x; ++j)
            if(r[j] > y) r[j] = y;
        for(rj j = x + 1; j <= n; ++j)
            if(l[j] < y) l[j] = y;
    }

按位贪心

一大类贪心

bzoj 4245

给定一个长度为n的序列a[1],a[2],...,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or ... or c[m]。请求出总费用的最小值。

1<=m<=n<=500000

根据位运算的性质，我们一位一位的考虑；

但是这又是分组问题，之前的分组会影响之后的决策；

怎么分，不好规定；但我们可以规定“不能怎么分”

我们统计所有数字这一位有多少个1；

1.奇数个1，我们怎么分都会剩下1，放弃；

2.没有1：永远出不来1；

3.偶数个1：我们可以分组，但是分组的要求是，剩下每组的1的数量都是偶数，所以如果对于一个数，它及它前面的1的数量为奇数，那么这个数不能和后面的数断开；

我们一共不能断开n-m个位置，将我们不要断开的位置与n-m比较，如果小于等于，这一位最后就可以是1；

皇帝的烦恼

由相邻两个人的颜色不能相同，答案至少为\max(a[i]+a[(i+1)modN])

再从颜色考虑，每种颜色最多给floor(n/2)个人，所以ans至少为ceil(sum/floor(n/2))

但是这个题的正解其实是DP，因为贪心...只能证明下界，不能证明上界；

叠罗汉

每个人有一个重量w，和力量s，每个人的危险度为\sum\text{在他上面的}w-s，求：把所有人都选上，重新排序，最小化危险度的最大值？

按w_i+s_i升序排序；

选出最多的人，使每个人的危险值<=0，最多选多少人？

按w_i+s_i升序排序，依次考虑加入每个人：如果他的s_i足够大，就加入，ans++；否则，考虑替换之前某个w_j>w_i的人（为了方便后面），可以维护一个大根堆；

为什么一定能替换呢？因为w_i+s_i升序，而w_i<w_j所以s_i>s_j；

P4552 IncDec Sequence

给定一个长度为n的数列{a_1,a_2,\cdots,a_n}，每次可以选择一个区间[l,r]，使这个区间内的数都加1或者都减1。

请问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

对于区间加减问题，可以先转化为差分数列；

也就是给我们一个数列，可以在一个地方+1，同时在一个地方-1，问使得整个序列为0的最小次数？（先不考虑第一个位置）

注意到负数需要+1，正数需要-1；

如果差分序列的和>0，答案是\sum|negative|+sum；否则，是\sum positive+|sum|；容易发现是正确的；

再来看最终的种类，我们可以任意变动a_1：如果差分序列的和>0，我们可以使a_i\in [-sum,0]，在这个范围内，答案不变，而再变小，答案就换了一种方法统计，会+1；同理，sum<0，a_i\in[0,sum]；

CF865D Buy Low Sell High

已知接下来N天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,当然,希望这N天内能够赚足够多的钱.

首先，为了保证手中不会残留股票，我们一定是每次要卖出时再考虑买入；

我们一定是优先卖出，但是有前提；

贪心策略：维护一个堆，表示前面的最小价格；

但是如果优先交易的话，会有这个问题：

考虑1,2,3...这组数据，显然最优解是1,3配对，而我们默认会让1,2配对，这就会出锅；

后悔堆！！！

当我们这天卖不了股票，就直接把这一天的价格price放入堆中；

否则，我们取出堆顶，ans+=price-top，然后，在堆中插入两次price！这样理解：第一个price代表：用后面更高的价格去购买top，这样多获得的利润是latersellprice-formersellprice，就相当于把今天的价格当成可以买入的；第二个price表示，如果你已经买了第一个price，这一天就什么都不做了，可以用来买入，为后面做准备；

    q.push(a[1]);
    for(ri i=2;i<=n;++i)
    {
        int t=q.top();
        if(t<a[i])
        {
            q.pop();
            ans+=a[i]-t;
            q.push(a[i]);
        }
        q.push(a[i]);
    }

CF1047C EnlargeGCD

给定一个1-N的序列，问最少删除几个数可以使整个序列的gcd变大；

方法：

现将所有数除以原序列的GCD，然后对每个数分解质因数，答案即为\min(n-num[i]),num[i]是质数i的出现次数；

POJ3270 Cow Sorting

对一个序列排序，交换任意两数的代价是两数之和，问使序列变成升序，最小的代价；

看到有关交换的排序，想到置换

每个置换一定是由很多环组成的；

对于每一个环，最优决策有：

以环内最小值为中转点，这样每个元素会被交换一次，而中转点交换cnt-1次；

以全局最小值为中转点，这样环内每个元素被交换一次，环内最小值交换两次，全局最小值交换cnt-1次；

POJ1201

题意：给定N个闭区间[a,b]和N个整数c_i，你需要从证书集合中选出一些数，使[a,b]中被选出来的数不少于c_i个，问最少选几个；

这道题可以差分约束做

我们考虑贪心，比如c_i都是1，这就变成了一道普及的贪心题：把区间按右端点排序，从左往右扫，每次在没覆盖的区间的最后一个位置放；

这道题类似，我们要在区间的最后的一些位置放，线段树维护；

重心

给定一棵树，每个点有权值，找到一个点，使得 权值 × 距离 的和最小；

这个点就是把sum作为size的树的重心；

BZOJ 3709

显然是先打加血的怪，按cost升序；

然后是掉血的怪，之前自己想的时候一直认为是按cost降序，但是看了分析之后恍然大悟；

我们要最小化扣血的最大值，设有两个怪，打的时候掉血分别为x1x2，打完之后加血分别为y1y2，并有x1>y1，x2>y2

考虑第一个怪排在第二个怪前面的条件，显然为max(x1,x1-y1+x2)<max(x2,x2-y2+x1)；

化简后为x1-y1+x2<x2-y2+x1，移项后达到y1>y2

ATC 2672 Coins

这道题真的太仙了

• 有X+Y+Z个人，每个人有Ai个金币，Bi个银币，Ci个铜币。现在 选X个人提供金币，Y个人提供银币，Z个人提供铜币。

• 求最多提供多少币。X+Y+Z≤100,000

费用流

我们先考虑一个简单的情况：只有两种币；

做法：先全部选择A，然后从中挑出y个A-B最小的，选择B；

现在有了三种币，怎么办？

我们要学会在简单的问题的基础上进行转化：

先按照A-B排序，这样我们选择的金币一定在前边，银币一定在后边，铜币混杂在中间；

看到前后分割的这么明确，我们就要想到枚举中间点，左边的用类似的策略选择A和C，右边的选择B和C，两边拼一起就是答案；

CF949D

这道题的题意非常的复杂；其实自己想的时候，也想到了能给一个点提供贡献的区间是连续的，然而一直不敢做出贪心的决策，看了题解才恍然大悟

首先，假如是奇数，中间的位置一定是能满足的；加入一个房间的人太多也没有关系；

然后，对于第i个考虑的点，能够提供贡献的区间分别是[1,i+i\times d];[n-i-i\times d +1,n]；

当两个区间不相交时，当然贪心的往两边跑，但是如果两个区间重叠，还是往一边跑会不会导致另一边的答案变小？并不会！

举例来说，之所以要往左边跑，因为左边的人数不够用了；也就说明右边的人数多，因此不需要左边的帮忙补充；

candy

有两个超市，每个超市有n(n≤10^5)个糖，每个糖W元。每颗糖有一个愉悦度，其中，第一家商店中的第i颗糖果的愉悦度为Ai，而第二家商店中的第i颗糖果的愉悦度为Bi。

在每家商店买的糖果会被打包到一个袋子中（可以在一家商店什么都不买，此时认为这家商店的袋子为空）。因为这两个袋子外观是一样的，所以会从两个袋子中随机选择一个，然后吃光里面的糖果。定义一种买糖果的方案的愉悦度为：吃到的糖果的愉悦度之和的最小可能值。

求买糖果的愉悦度与买糖果的花费之差的最大值。

首先我们选择的一定是权值上最大的那些糖果；于是我们从大到小排序，做一遍前缀和，然后枚举每个前缀和成为答案，计二分对应的另一边糖果需要的数量；

但事实上，我们不会选择所有val<w的糖果；

USACO出租车

很玄学的排序，但是模拟一下发现确实是这样，先把每条路的长度加上，然后把起点终点分别排序，将0视为终点，1视为起点，答案加上相邻两个起点终点的绝对值之差；

[CQOI2017]小Q的棋盘

最优解一定是在树上随意走，然后回来，然后向最长链里走，不回来；