Greedy & Violent

贪心可不是件简单事儿.

有趣的贪心

依据与思想

  1. 贪心既然是一个方向的dp,往往相邻交换法可以得到优先级

  2. 真正不要脑洞的贪心还是很少的(比如例题11,UVA11520)

    ​

    贪心法是每步选择局部最优解，然后一步一步向目标迈进。这个“目标”两字很关键，说明贪心法是目标导向的，每一步的方向一定是目标。那么我上面两种方法其实只是在模仿那个经典问题的模式，但是却没有时刻注意到这个问题最终目标是实现从1到n每一位都能放上满足条件的车，比如第二个反例最后一个格最后都无法放车了，就是因为前面没有按照对最终目标的影响效果去选择局部最优解，单纯的选最左边一个是毫无道理的，因为本题已经不是那个经典的选最少点的问题了。(UVA11134题解摘录)

热身训练

sort大法好==.

  1. HEllo World (2 ^ ans > n)

  2. CF363A最小碰撞时间

  3. Building designing sort两个指针扫

  4. Ancient Cipher sort计数

  5. DNA Consensus String 枚举

  6. Big Chocolate 找规律==

  7. All in All 两个指针扫

  8. Children’s Game(UVA10905) 字符串最大==sort by a + b > b + a

  9. UVA11389 给出两个数组,使得搭配后所有超出S的值 超出部分和最小

  10. 例题1 UVA11292 勇者斗恶龙,两个指针往后扫

    加上这两句话(if)才能过???

    1
    2
    if(n) sort(dg, dg + n);
    if(m) sort(hero, hero + m);
    • 进阶 LA3266 田忌赛马
    • (这个我CSDN博客有详细题解==
    • 当初放弃ACM Steps题目..现在看来脸皮厚多了)

  11. UVA11100 (进阶)个数尽量少严格递增…等差(距)数列

  12. LA4094(进阶) 梦之队 这道题网上题解分析很贪心hhh

  13. LA4636(进阶) 给出主视图和左视图,求最小立体…(每次找max,相等加到ans,不相等舍弃大的那个)

  14. LA3303 相邻交换法 a1b2 < a2b1

  15. LA2757 从后向前

区间问题

最早完成

  1. 例题2 UVA11729 Bi时间交代任务,Ji时间完成. ==> (交换法证明)完成时间长的先交代

  2. 例题10 UVA11384 用最少次数全部变成0 =>> 保持平衡 ,每次把大的一半减去(n/2)+1

    递归/二分(每次减大的数的一半)

最少区间选择

  1. UVA10382 sort by zuo when equal by you

最多区间选点

  1. UVA11134 二维的..等价于两个一维,紫书P237
  2. Priest John’s Busiest Day 至少出席区间一半时间 因为左右等价,sort by middle

最小惩罚

  1. LA4850 求两个最大惩罚之和,end排序贪心扫一遍后,枚举

    做法一: 枚举一个任务以及调动位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    struct seg
    {
        int f,e;
        bool operator<(const seg & b)const{
            return e < b.e;
        }
    }cs[500 + 5];
    /* in main
      sort(cs, cs + n);
     > int ans = gao(-1,10000,n);
     > for(int i = 0;i < n;i++)//枚举一个任务调动
     >   for(int j = 0;j < n;j++)//枚举调动位置
     >     ans = min(ans,gao(i,j,n));
     > printf("%d\n", ans);
    */
    int gao(int cur,int to,int n)
    {
       int sum = 0, cnt = 0;
       int max1 = 0,max2 = 0;
       for(int i = 0; i <= n; i++)
       {
           if(cnt == to)
           {
               sum += cs[cur].f;
               max2 = max(max2,sum - cs[cur].e);
               if(max2 > max1) swap(max2,max1);
           }//调动位置
         
           if(i != cur && i < n)
           {
                 sum += cs[i].f;
                 max2 = max(max2,sum - cs[i].e);
                if(max2 > max1) swap(max1,max2);
                cnt++;
            }//未调动位置
        }
        return max1 + max2;
    }

剪枝

牺牲的任务只能在两个最大惩罚值中的最后一个任务的前面，只有牺牲前面的任务才能使最大惩罚值的值减小，注意这里是牺牲，就表示有可能牺牲这个任务后，该任务的惩罚值变成了最大惩罚值的其中一个。

​

方法2 二分套二分

半边界

优先队列维护

  • LA3507 知道DDL和花费,用优先队列维护最优值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans += af[i].q;
      dd.push(af[i].q);
      while (ans > af[i].d) {
        ans -= dd.top();
        dd.pop();
      }
    }

    ​

路径最小

  1. 例题3 UVA11300 所有人转手金币之和最小

    1. (少一个方程的线性方程组=>)单变量极值不等式
    2. 数轴上一串点距离和,中位数是极小值点.

  2. 例题4 LA3708 加入m个雕塑到n个等距中,求最小移动距离

    1. 变换坐标系为len = 1;
    2. tot最小,一定移动到最接近的位置
    3. 随机选一个坐标原点不动
    1
    2
    3
    //坐标缩小后就可以更方便的选择
    double pos = (double)i / n * (n + m);//原来雕像的位置
    ans += fabs(pos - floor(pos + 0.5))/(n + m);//*n+m后就选四舍五入最近的

相对不变问题

  1. 例题5 UVA10881 蚂蚁爬.求每个蚂蚁最后的位置和方向

    每个蚂蚁的相对顺序不会改变=>记录id,最后对应回去

    1
    2
    3
    4
    sort(before, before + n);
    for (int i = 0; i < n; i++) {
      order[before[i].id] = i;
    }// 之后i := 0->n, a = order[i]就是从小到大的顺上去

树形贪心

  1. 例题15 LA3902

    每个叶节点不超过k有个站

    求站的最小数

    ​

    每次取最深的

    通过node表flood fill.

    (node[dis]表示深度为dis的叶子))

    ​

    1
    2
    3
    for(int i = 0;i < k;i++) v = fa[v];//第k级祖先

    if (e[u].size() == 1 && d > k) node[d].push_back(u);//node表构建

  2. CF363c 完全二叉树..每次找最近公共祖先还是很简单的==

左右互搏法

  1. 例题16 LA3177

围成一个圈每个人拿r[i]个礼物,相邻不相同

  1. n == 1,特殊情况总共r[1]个
  2. ​n % 2 == 0 => max(r[i] + r[i+1])个
  3. n % 2 == 1
    1. 二分答案
    2. 以r[1]为界限循环一圈,(除了第一个)奇数尽量拿右边的,偶数尽量拿左边的,
    3. (因为第一个和最后一个都是奇数位)看最后一个是否会拿左边的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool check(int p)
{
    int x = a[1], y = p - a[1];//bound
    left[1] = x,right[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (i & 1)
        {
            right[i] = min(a[i],y - right[i-1]);//奇数尽量拿右边的
            left[i] = a[i] - right[i];
        }
        else
        {
            left[i] = min(a[i], x - left[i-1]);//偶数尽量拿左边的
            right[i] = a[i] - left[i];
        }
    }
    return left[n] == 0;
}

  • UVA11627(数据有毒) 过障碍维护当前最左和最右

  • LA4725 两个飞机一个入口,问最小编码..维护当前飞机,ab能飞和tot能飞

    维护当前机场的飞机数目，机场可以供起飞的数目还有可以起飞的总数。

    超过数目后，判断可供起飞的数目是否为0就行了。

    其实也就是因为a起飞数和b起飞数不是完全相干的

    所以要多个变量定义.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    inline int min(int a,int &b,int &c)
    {
        if (a > b) {
            if (b > c)
                return c;
            return b;
        }
        if (a > c)
            return c;
        return a;
    }
    bool ok(int m){//high cnt = m
        int ap = 0,bp = 0;//当前飞机场数目
        int af = 0,bf = 0,tf = 0;//a可以起飞数,b,总
        for (int i = 0; i < n; i++) {
            if(a[i] > m || b[i] > m) return false;
            ap += a[i];//时间i降落
            bp += b[i];
            if(ap > m)//之前起飞
            {
                int dec = min(ap - m, af,tf);
                ap -= dec,af -= dec,tf -= dec;
            }
            if(bp > m) {
                int dec = min(bp - m, bf,tf);
                bp -= dec,bf -= dec,tf -= dec;
            }
            if(ap > m || bp > m) return false;
            if(af < ap) af++;//主要是这个if限制了状态定义
            if(bf < bp) bf++;
            if(tf < ap + bp) tf++;
        }
        return true;
    }

  • LA3403 (紫书例题)天平难题…二进制枚举二叉树,记录左右最大值

滑动窗口/单调队列

  1. 例题18 UVA11078 找Ai和Aj使得Ai - Aj尽量大

    维护小于j的最大i值 MaxAi = max(Aj,MaxAi)

  2. 例题21 LA2678 正整数序列,求最短子序列和>S

    • 重点在于随后加一个if (ans == maxn) ans = 0

    尺取法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (ptr1 = ptr2 = 0; ptr2 < N; ptr2++) {
      sum += a[ptr2];//每次后面的指针后移
      while (ptr1 <= ptr2 && sum - a[ptr1] >= S)
      {
        sum -= a[ptr1];
        ptr1++;
      }
      if (sum >= S)update(ans, ptr2 - ptr1 + 1);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (ptr1 = ptr2 = 0; ptr2 < N; ) {
      while (sum < S && ptr2 < N ) {
        sum += a[ptr2];
        ptr2++;
      }
      while (sum >= S && ptr1 < ptr2) {
        update(ans, ptr2 - ptr1);
        sum -= a[ptr1];
        ptr1++;
      }
    }

可怕的暴力

三维问题

  1. 例题6 LA2995 (最大立体)三维坐标系转换

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void get(int k, int i, int j, int len, int &x, int &y, int &z)
    {
      if (k == 0) { x = len; y = j; z = i; } 
      if (k == 1) { x = n - 1 - j; y = len; z = i; }
      if (k == 2) { x = n - 1 - len; y = n - 1 - j; z = i; }
      if (k == 3) { x = j; y = n - 1 - len; z = i; }
      if (k == 4) { x = n - 1 - i; y = j; z = len; }
      if (k == 5) { x = i; y = j; z = n - 1 - len; }
    }
    /*	给出六个面
    	k: 前 左 后 右 顶 底
    	i j 枚举位置
    	len是深入的长度
    	x y z从上往下看的坐标系
    */

  2. 例题8 LA3401 修改最少的面使得立方体相同

    1. 写个小程序枚举”姿态”
    2. 枚举每个立方体每种姿态最少涂色数

套路

  1. 例题7 UVA11464 01矩阵枚举第一行

  2. 例题11 UVA10795 汉诺塔的扩展

    汉诺塔变形,给出始态终态,求移动步数

    赋予中间态定义f(P,i,final)表示把1…i全部移动到final所需要的步数

    ans = f(start,k-1,6-start[k]-finish[k]) + f(finish,k-1,6-start[k]-finish[k])+1

    (k 是最大编号要移动的盘子)

    f(P,i,final) = (P[i] == final) ? f(P , i-1, final): f(P,i-1,6-P[i]-final) + (1LL<<(i-1));

  3. 例题17 计数排序

  4. 例题19 UVa11549 Floyd判圈法

    1
    2
    3
    4
    5
    6
    long long a = k,b = k;
    do{
      a = next_num(a);
      b = next_num(b); if(b > ans) ans = b;
      b = next_num(b); if(b > ans) ans = b;
    }while (a != b);

  5. 例题24 三维最大子空间

二分

二分模板= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//整数
while(l < r)
{
  int m = l + (r - l + 1) / 2;
  if(check(m)) l = m;
  else r = m - 1;
}
l is answer
  
//浮点数
while (r - l > 0.000001) {
  double m = (r + l )/2;
  if (check(m)) {
    l = m;
  }else
    r = m;
}

//单调时最小位置
i = lower_bound(a,a + n,val) - a;
  1. 例题12 最小品质因子最大值最小a值最大b
  2. LA4254 白书手写题解==
  3. LA4253 返回值有意义的二分(判存在性,极角维护左右)

二维降,扫描线

  1. 例题20 LA3905 流星最多的时间

    1. 扫描线计数法(碰到起点+1)
    2. 抽象为起点和终点,由于是直线,二维= 一维∩一维
    3. 整数计算

  2. 例题23 LA3695 找一个矩形边上包括尽量多的点

    求平行坐标轴的矩形边上最多点覆盖

    扫描线,对所有点依据x排序,对所有y排序,unique

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    for (int a = 0; a < m; a++) {
      for (int b = a + 1; b < m; b++) {
        int low = y[a], high = y[b];//枚举平行于x轴的两条边
        int k = 0,M = 0;
        for (int i = 0; i < n; i++) {//扫描平行于y轴的边
          if (i == 0 || p[i].x != p[i-1].x) {
            k++;//统计x坐标个数
            on[k] = on2[k] = 0;
            left[k] = k == 0 ? 0 : on2[k-1] - on[k-1] + left[k-1];//y = low (+) high 上已经有多少点
          }
          if(p[i].y > low && p[i].y < high) on[k]++;//左记录线记录low,high之间的边(不含端点)
          if(p[i].y >= low && p[i].y <= high) on2[k]++;//右记录线记录low,high之间的边(含端点)
        }
        if(k <= 2) return n;//总共只有两个坐标(这里不用再对x排序- -)
        for (int j = 1; j <= k; j++) {
          ans = max(ans,on2[j] + M + left[j]);//ans = max(on2[j] + on2[j-1] + left[j] - left[j-1])
          M = max(M,on[j] - left[j]);//维护on[i] - left[j]的最大值
        }
      }
    }

悬线法

  1. 例题22 LA3029 最大子矩阵.

    把每个格子向上延伸的连续空格看成一条悬线

    有障碍物的区域中的最大子矩阵

    (USACO用一个height数组过的(USACO6.1))

    训练指南是维护up,l,r三个数组,l,r标记以up为高度的矩形最左和最右的位置

01 GUY

  1. 例题25 LA2965 尽量多的串使得大写字母都出现偶数次

    • =>用二进制位表示字母
  • =>xor == 0
  • =>枚举前一半,而后枚举后一半中途相遇

码农题

  1. 例题9 UVA11210 麻将(判断”听牌”)

  2. Ugly Windows 代码量不大但是有坑

  3. LA3667 最少刻度 二进制bfs扩展参考

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    for (i = 0; i < N; i++) {
      if (cur.found & (1<<i)) continue;//当前存在
      int v = *iter + arr[i];//扩展节点
      if(cur.st.find(v) != cur.st.end()) continue;
      if(v > MAX) continue;
      next = cur;
      next.st.insert(v);
      for (set<int>::iterator iter2 = cur.st.begin();//进一步扩展
           iter2 != cur.st.end(); iter2++) {
        int x = abs(v - *iter2);
        if (idx[x] != -1) {
          next.found |= (1<<idx[x]);
        }
      }
      if (next.found != cur.found) {
        q.push(next);
      }
    }

    ​

  4. UVA10825 乘2..m后所有位数字还是那些…..枚举最后一位生成所有位数

  5. LA3621 最少几次乘除得到${X}^{n}$.迭代加深搜索+剪枝

trick

  1. writein & readin

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    inline int readint()
    {
    	char c = getchar();
      	while(!isdigit(c)) c = getchar();
      	
      	int x = 0;
      	while(isdigit(c)){
      		x = x * 10 + c - '0';
          	c = getchar();
    	}
      	return x;
    }
    int buf[10];//global varible

    inline void writeint(int i)

    {

      int p = 0;

      if(i == 0)p++;
      else while(i)
      {
        buf[p++] = i % 10;
        i /= 10;

      }

      for(int j = p - 1;j >= 0;j--) putchar('0' + j);

    }

  1. 例题及习题指 <<算法竞赛入门经典(训练指南)>>对应例题

  2. 私在vjudge中开题集(因为uva墙外服务器是在是慢啊…)

  3. 求LA5704 Yummy Triangular Pizza传统题解,oeis是个好地方

本文标题:Greedy & Violent

文章作者:Renld

发布时间:2016年07月22日 - 17时46分

最后更新:2016年07月22日 - 22时41分

原始链接:http://renld.github.io/2016/07/22/greedy/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 有趣的贪心
    1. 1.1. 依据与思想
    2. 1.2. 热身训练
    3. 1.3. 区间问题
      1. 1.3.1. 最早完成
      2. 1.3.2. 最少区间选择
      3. 1.3.3. 最多区间选点
      4. 1.3.4. 最小惩罚
      5. 1.3.5. 半边界
    4. 1.4. 路径最小
    5. 1.5. 相对不变问题
    6. 1.6. 树形贪心
    7. 1.7. 左右互搏法
    8. 1.8. 滑动窗口/单调队列
      1. 1.8.0.1. 尺取法
  • 2. 可怕的暴力
    1. 2.1. 三维问题
    2. 2.2. 套路
      1. 2.2.1. 二分
      2. 2.2.2. 二维降,扫描线
      3. 2.2.3. 悬线法
      4. 2.2.4. 01 GUY
    3. 2.3. 码农题
    4. 2.4. trick