贪心算法

贪心的题基本上就是数学问题，有的时候也真的是靠直觉…所以还是从一些例题里面找找感觉吧。

（1）NOIP200205均分纸牌

难度级别：A； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B

试题描述

 有 N 堆纸牌，编号分别为 1，2，…， N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
    例如 N=4，4 堆纸牌数分别为：  ①　9　②　8　③　17　④　6
    移动3次可达到目的：从 ③ 取 4 张牌放到 ④ （9  8 13  10） -> 从③ 取 3 张牌放到 ②（9  11 10  10）-> 从② 取 1 张牌放到①（10  10 10  10）。

输入

第一行：N（N 堆纸牌，1 <= N <= 100）
第二行：A1  A2  …  An （表示 N 堆纸牌，每堆纸牌初始数，均大于零且不超过10000），两两之间有一个空格分隔。

输出

一个数，表示各堆纸牌数均达到相等时的最少移动次数 

输入示例

4
9 8 17 6

输出示例

3

思路大致如下：

首先，要把每堆牌都移动到一样为止，那么肯定要先求出平均值。

其次，为了简化问题，会想到一种方法，即：以平均值为准，所有纸牌的初始值比平均值多的记为正，比平均值少的记为负。

最后，用一个for循环，从左到右依次让当前位置达到“0”，即平均值。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[101],b[101];
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);sum+=a[i];}
    int tot=sum/n;
    for(int i=1;i<=n;i++) b[i]=a[i]-tot;   //正数表示多了几个，负数表示少了几个
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]==0) continue;
        if(b[i]>0)
        {
            b[i+1]+=b[i];
            b[i]=0;
        }
        else
        {
            b[i+1]-=0-b[i];
            b[i]=0;
        }
        ans++;
    }
    printf("%d",ans);
    //system("pause");
    return 0;
}

 

Simple game

给 n，m，求一个数 a(1 ≤ a ≤ n), 使得当 c 在 1 到 n 的整数中 随机取值时,|c − a| < |c − m| 成立的概率最大。

范围：1 ≤ n, m ≤ 10的9次方

首先联想到，某两个数相减所得的绝对值的几何意义就是两点间的距离。

之后就不同情况讨论，找出最佳位置。

如图，若：

1.a在M左侧，且c在a左侧时，概率为100%；

2.a在M左侧，且c在a右侧、M左侧时，概率约等于50％；

3.a在M左侧，且c在a右侧、M右侧时，概率根据n-m的值而定；

……

之后我们发现，当“a在M左侧，且c在a左侧”以及“a在M右侧，且c在a右侧”时概率均为100％。所以要尽可能加大这两种情况。也就是，a选择在M两侧最靠近M的两个点上的时候。

 

（3）Woodcutters

给 n 棵树在一维数轴上的坐标，以及它们的高度。现在要你砍倒 这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然 也不能覆盖其他的树原来的位置，现在求最多可以砍倒的树的数目。

1 ≤ n ≤ 105 , 1 ≤ xi , hi ≤ 109

看上去非常奇怪的一道题，所以也放了上来。（毕竟脑补那种一排树突然一下全都整齐的倒了下去……真是画风清奇）

其实思路很简单啦，就是不要想得太复杂。

从左往右考虑，当前树能不能往左倒？如果不能就直接往右倒好了，不用管后面的树。（因为这棵不倒，下一棵也要倒嘛，所以就考虑当下就行了）

特别的，最左和最右边的树肯定是往两边倒。

 

Team

构造一个 01 序列，包含 n 个 0，m 个 1 要求不存在连续 2 个 0，或 3 个 1

1 ≤ n, m ≤ 106

又是一道看起来很奇怪的题目。因为乍一看，觉得不知道从哪入手啊。

其实贪心这个东西，很多时候都类似于：在一大堆东西里挑出最好的几个（或是挑出所有让自己满意的），其他的就扔下不管了。

这道题就是后者。

既然是2个0、3个1，那么为了充分利用所有的数字（也就是所谓的贪心），1的个数明显要比0多。那么如果给的m比n小，就不用考虑了。

判断完了，可以用‘10’和‘110’构造序列。（应该一看就能明白吧…）