贪心笔记

例一：给定长度为n的整数数列{Aj}，找出两个整数ai和aj(i<j)，使得ai-aj尽量大

#include<bits/stdc++.h>
using namespace std;
int main() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tmp = min(aj);
			ans = ai - tmp
		}
	}
}

//贪心：ai一定的情况下，aj尽可能小min
//枚举优化——后缀最小值（后i个数的最小值）：维护minn[i]
//for (i = n; i >=1; i--){
//  minn[i] = min(minn[i+1], a[j])
// 
// for (i = 1; i <= n; i++)
//  ans =  max(ai - minn[i+1])
//  优点：只需要循环i一次，j用minn[i]替代了

例二：NC16783 拼数

当一个字符串是另一个字符串的子串时，无法通过直接比较字典序来排序。

解法 —— 任取两个字符串双向拼接，比较效果，这样可以同一字符串的长度

#include<bits/stdc++.h>
using namespace std;
int n;
string s[100];
bool comp(string a, string b)
{
    return a+b > b+a;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    sort(s+1,s+1+n,comp);
    for (int i = 1; i <= n; i++)
        cout << s[i];
    return 0;
}

例三：NC10733 cf489C Given Length and Sum of Digits...

求长度为m，每一位数字的和为S的最大数和最小数

m <= 100, S <= 900

思路：

先判断无界：10000不行，或者全是9也不行（不满足S）

最大值：能放9高位就放9，不能放9放较大的数，直到没有了全部补0

最小值：把找到的最大值反过来，把首位的0改成1，最后一个0后面的那个数减1

例四：NC16618 排座椅

#include<bits/stdc++.h>
using namespace std;
int m, n, k, l, d;
// m行 n列 横向通道（隔开相邻行 k条  纵向通道l条
//d对说话的同学
struct ty
{
    int pos, num;
} heng[1200], zong[1200];

bool comp1(ty x, ty y)
{
    return x.num > y.num;
}

bool comp2(ty x, ty y)
{
    return x.pos < y.pos;
}

int main()
{
    scanf("%d%d%d%d%d", &m, &n, &k, &l, &d);
    for (int i =1; i <= max(m,n); i++)
        heng[i].pos = i, zong[i].pos = i;
    for (int i = 1; i <= d; i++)
    {
        int x, y, p, q;
        scanf("%d%d%d%d", &x, &y, &p, &q);
        if (x == p) zong[min(y, q)].num++;
        else heng[min(x, p)].num++;
    }
    sort(heng+1, heng+1+m, comp1);
    sort(zong+1, zong+1+n, comp1);
    
    sort (heng +1, heng+1+k, comp2);
    sort (zong +1, zong+1+l, comp2);
    for (int i = 1; i <= k; i++)
        printf("%d ", heng[i].pos);
    printf("\n");
    for (int i = 1; i <= l; i++)
        printf("%d ", zong[i].pos);
    return 0;
}

例五：NC200190 矩阵消除游戏

行列之间有交叉，不能贪心

行与行之间，列于列之间无交叉，可以贪心

————暴力枚举哪些行

例六：区间覆盖（工作安排）

在0到L的数轴上有n个区间[li,ri]，现在需要你选出其中尽量多个区间，使得其两两不相交(n<=100000)

思路：优先选右端点小的（给其他的留出了更多的机会）

例七：活动安排

给n个活动，每个活动需要一段时间Ci来完成，并且有一个截止时间Di，当完成时间ti大于截止时间完成时，会扣除ti-Di分，让你找出如何使自己所扣分的最大值最小。

思路：交换任意两个相邻的活动AB（不影响其他活动的相对顺序）

设A在B前更优：

A在B之前时：