0x07 内容简介与例题习题

贪心的基本思想

【例题】防晒（AcWing110）【例题】国王游戏（AcWing114） 未完成题目

【例题】给树染色（AcWing115）【练习】任务（AcWing127）

贪心是一种在每次决策时采取当前意义下最优策略的算法。一般通过猜测得出策略之后，加以证明即可使用。通常的证明方法有以下几种：
反证法
邻项交换法（通过交换相邻两项，证明原决策比交换之后的决策更优）
决策包容性
范围扩展（证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差）

那我们直接来看几道例题吧。

题目链接
思路：
首先给出贪心策略：按照 m i n s p f minspf minspf递减的顺序把奶牛排序，依次考虑每只奶牛。对于每头奶牛，找到一瓶还有剩余的且 s p f spf spf值最大的防晒霜去用。
接下来我们来证明这个策略的正确性。这里使用范围扩展证明，考虑这一步策略的作用范围扩展到其他奶牛之后的影响。由于奶牛已经按照 m i n s p f minspf minspf值递减的顺序排序，所以每一瓶大于当前奶牛 m i n s p f minspf minspf值的防晒霜，都会大于之后奶牛的 m i n s p f minspf minspf值。那么也就是说， 对于当前奶牛可以使用的任意两瓶防晒霜而言，假设这两瓶防晒霜是 x , y x,y x,y，如果 s p f x < s p f y spf_{x}

AC代码：

#include
#define N 2505

using namespace std;

int n,m;
struct node{
    int mi,mx;
    bool operator < (const node& c)const{
        return mi > c.mi;
    }
}cow[N];

struct Node{
    int spf,cover;
    bool operator < (const Node& b) const{
        return spf > b.spf;
    }
}spfs[N];

void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
        cin >> cow[i].mi >> cow[i].mx;
    for(int i = 1;i <= m;i ++)
        cin >> spfs[i].spf >> spfs[i].cover;

    sort(cow + 1,cow + 1 + n);
    sort(spfs + 1,spfs + 1 + m);

    int ans = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(spfs[j].spf <= cow[i].mx && spfs[j].spf >= cow[i].mi && spfs[j].cover){
                ans ++;
                spfs[j].cover --;
                break;
            }
        }
    }

    cout << ans << endl;
}

int main(){
    solve();
    return 0;
}

题目链接
思路：
首先给出贪心策略，按照每个大臣左、右手上数的乘积从小到大排序，就是最优排队方案。
接下来使用邻项交换法证明这个策略的正确性。
对于任意一种排队顺序，设 n n n名大臣左右手上的数字分别是 A [ 1 ] . . . A [ n ] A[1]...A[n] A[1]...A[n]与 B [ 1 ] . . . B [ n ] B[1]...B[n] B[1]...B[n]，国王手里的数字是 A [ 0 ] A[0] A[0]与 B [ 0 ] B[0] B[0]
假设我们交换顺序的两位大臣是 i i i和 i + 1 i + 1 i+1，那么在交换之前这两位大臣获得的奖励分别为：
1 B [ i ] ∗ ∏ j = 0 i − 1 A [ j ] frac{1}{B[i]}*prod limits_{j=0}^{i-1}A[j] B[i]1​∗j=0∏i−1​A[j]与 A [ i ] B [ i + 1 ] ∗ ∏ j = 0 i − 1 A [ j ] frac{A[i]}{B[i + 1]}*prod limits_{j=0}^{i-1}A[j] B[i+1]A[i]​∗j=0∏i−1​A[j]
交换之后两位大臣获得的奖励为：
1 B [ i + 1 ] ∗ ∏ j = 0 i − 1 A [ j ] frac{1}{B[i+1]}*prod limits_{j =0}^{i-1}A[j] B[i+1]1​∗j=0∏i−1​A[j]与 A [ i + 1 ] B [ i ] ∗ ∏ j = 0 i − 1 A [ j ] frac{A[i+1]}{B[i]}*prod limits_{j=0}^{i-1}A[j] B[i]A[i+1]​∗j=0∏i−1​A[j]
我们要比较交换前后的最大值变换情况，其实就是比较下面两个式子：
m a x ( 1 B [ i ] , A [ i ] B [ i + 1 ] ) max(frac{1}{B[i]}, frac{A[i]}{B[i+1]}) max(B[i]1​,B[i+1]A[i]​)与 m a x ( 1 B [ i + 1 ] , A [ i + 1 ] B [ i ] ) max(frac{1}{B[i +1]}, frac{A[i+1]}{B[i]}) max(B[i+1]1​,B[i]A[i+1]​)
我们把他们同时乘上 B [ i ] ∗ B [ i + 1 ] B[i]*B[i+1] B[i]∗B[i+1]得到：
m a x ( B [ i + 1 ] , B [ i ] ∗ A [ i ] ) max(B[i+1], B[i]*A[i]) max(B[i+1],B[i]∗A[i])与 m a x ( B [ i ] , B [ i + 1 ] ∗ A [ i + 1 ] ) max(B[i], B[i+1]*A[i+1]) max(B[i],B[i+1]∗A[i+1])
由于所有的数都是正整数，那么 B [ i + 1 ] ≤ B [ i + 1 ] ∗ A [ i + 1 ] B[i+1] le B[i+1]*A[i+1] B[i+1]≤B[i+1]∗A[i+1]， B [ i ] ≤ B [ i ] ∗ A [ i ] B[i]le B[i]*A[i] B[i]≤B[i]∗A[i]
所以只有当 A [ i ] ∗ B [ i ] ≤ A [ i + 1 ] ∗ B [ i + 1 ] A[i]*B[i]le A[i+1]*B[i+1] A[i]∗B[i]≤A[i+1]∗B[i+1]，交换前更优。也就是说，只要存在逆序对，那么交换逆序对可以使得情况变优。当无法交换也即按顺序时，为最优局面。得证。
使用这个贪心策略之后，用高精度写一下就好了。（高精好麻烦呜呜呜

AC代码：

#include 
#include 
#include 

using namespace std;

typedef pair PII;

const int N = 1005, base = 10000;

PII nums[N];

void output(vector& a)
{ 
    printf("%d", a.back());
    for (int i = a.size() - 2; i >= 0; i -- )
        printf("%04d", a[i]);
    puts("");
}

vector mul(vector a, int b)
{
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        a[i] = a[i] * b + t;
        t = a[i] / base;
        a[i] %= base;
    }
    while(t)
    {
        a.push_back(t % base);
        t /= base;
    }
        
    return a;
}

vector div(vector a, int b)
{
    int t = 0;
    for (int i = a.size() - 1; i >= 0; i -- )
    {
        a[i] += t * base;
        t = a[i] % b;
        a[i] /= b;
    }
    while(a.size() && a.back() == 0) a.pop_back();
    if (a.size() == 0) a.push_back(0);
    return a;
}

vector max_vec(vector a, vector b)
{
    if (a.size() == b.size())
    {
        for (int i = a.size() - 1; i >= 0; i -- )
            if (a[i] > b[i]) return a;
            else if(b[i] > a[i]) return b;
        return a;
    }
    else if(a.size() > b.size()) return a;
    else return b;
}

int main()
{
    int n;
    scanf("%d", &n); 
    for (int i = 0; i <= n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        nums[i] = {a * b, b};
    }
    sort(nums + 1, nums + 1 + n);
    
    vector res(1, 1);
    vector ans(1, 0);
    for (int i = 0; i <= n; i ++ )
    {
        if (i)
    	{
    		ans = max_vec(ans, div(res, nums[i].second));
		}
        res = mul(res, nums[i].first / nums[i].second);
	}
    
    output(ans);
    
    return 0;
}