算法思想精练：贪心、二分、正难则反及背包问题

2. 语文成绩

题目：P2367 语文成绩

解法：差分

这道题就是一道差分的模板题目，不断维护（+ -）区间内的所有内容（学生成绩），然后用前缀和还原数组，一边还原，一边求最小值。

代码：

#include<iostream>
using namespace std;
const int N = 5e6+10;
int n, p;
int f[N];
int main(){
    cin >> n >> p;
    for(int i = 1; i <= n; i++)//差分数组
    {
        int x; cin >> x;
        f[i] += x;
        f[i + 1] -= x;
    }
    while(p--)//维护差分数组
    {
        int x, y, z; cin >> x >> y >> z;
        f[x] += z;
        f[y + 1] -= z;
    }
    int ret = 1e9;
    for(int i = 1; i <= n; i++)//前缀和还原数组
    {
        f[i] += f[i - 1];
        ret = min(ret, f[i]);
    }
    cout << ret << endl;
    return 0;
}

3. 跳跳

题目：P4995 跳跳！

解法：贪心

先从小到大进行排序，每次都跳距离当前位置最远的位置（h 差最大），左右跳，用双指针（下标）更新。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 310;
int n;
LL h[N];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    sort(h + 1, h + 1 + n);
    int l = 0, r = n;
    LL sum = 0;
    while(l < r){
        sum += (h[l] - h[r]) * (h[l] - h[r]);
        l++;
        sum += (h[l] - h[r]) * (h[l] - h[r]);
        r--;
    }
    cout << sum << endl;
    return 0;
}

4. 数列分段 Section II

题目：P1182 数列分段 Section II

解法：二分答案

看到题目的关键词'最大值最小'，立马想到二分算法，并且也可以写出二段性： 当分的段数越多的时候，最大的和越小； 当分的段数越少的时候，最大的和越小。 因此，可以用二分答案来解决。

关于（计算）calc 函数，传入一个和 x，求出最少能分多少段： 从前往后累加，只要和小于 x，就一直加；（这里用 long long，防溢出） 直到和超过 x，之前的为一段，然后从该位置继续累加。注意：最后要额外加一段（最后一段）。

代码：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int n, m;
LL a[N];
int calc(LL x){
    int cnt = 0, sum = 0;
    for(int i = 1; i <= n; i++){
        sum += a[i];
        if(sum > x){
            cnt++;
            sum = a[i];
        }
    }
    return cnt + 1;//划分后，最后还有一段
}
int main(){
    cin >> n >> m;
    LL l = 0, r = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        l = max(l, a[i]);
        r += a[i];
    }
    while(l < r){
        LL mid = (l + r) / 2;
        if(calc(mid) <= m) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

5. 修理牛棚

题目：P1209 [USACO1.3] 修理牛棚 Barn Repair

解法：正难则反 + 贪心

这道题既要求了木板数有限，有要求了木板长度最短，如果挨个考虑放置每个木板的话，非常复杂，用 dfs 暴搜会超时。那么，我们将问题转化（逆向思维）：先放一块长木板，考虑中间的间隔，m 个木板，就有m - 1 个间隔，（c 头奶牛，最多间隔数 c - 1）。用贪心：排序，优先考虑处理间隔较长的，这样用的木板总长度最短。模板长度：a[c] - a[1] + 1。

代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 210;
int m, s, c;
int a[N];//奶牛所占牛棚编号
int b[N];//间隔
bool cmp(int a, int b){
    return a > b;
}
int main(){
    cin >> m >> s >> c;
    for(int i = 1; i <= c; i++) cin >> a[i];
    sort(a + 1, a + 1 + c);
    for(int i = 1; i < c; i++){
        b[i] = a[i + 1] - a[i] - 1;
    }
    sort(b + 1, b + 1 + c, cmp);
    int ret = a[c] - a[1] + 1;
    for(int i = 1; i < m && i < c; i++){
        ret -= b[i];
    }
    cout << ret << endl;
    return 0;
}

6. 货币系统

题目：P5020 [NOIP 2018 提高组] 货币系统

解法：完全背包（动态规划）

由题目'无穷多张'，可以想到用完全背包解题。

题意：就是在一堆数中选几个数能够表示其他所有的数（货币表示问题），选出最少的数组个数。

性质：1.由于较大的数只能较小的数（<=）表示，那么可以先对所有的数升序排序；2.如果一个数 i 能被 [i, i - 1] 区间内的数表示，就可以舍去，如果不能，就保留。

于是，先排序，这道题目就转化为完全背包问题：

1.状态表式： bool f[i][j] 从前 i 个纸币挑选，能否凑成总和为 j;

状态转移方程： f[i][j]：1.不选，f[i - 1][j]; 2.选，f[i][j - a[i]] 用 ||(二者满足其一即可)；

初始化： f[0][0] = true，方便用于后面更新正确；

填表顺序： 第二层（for 循环），完全背包，从小到大；

结果确定： 因为更新到这个数 i 之后，i 一定能被本身表示，所以后面 i 一定会变为 true，一边循环，一边更新结果（在第二层开始之前，第一层），如果 f[a[i]] == 0，就是还不能被表示出来，结果 +1。

多组数据测试，每次要清空。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110, M = 25010;
int n;
int a[N];
bool f[M];
int main(){
    int T; cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        memset(f, 0, sizeof f);//清空数据
        f[0] = true;
        int ret = 0;
        for(int i = 1; i <= n; i++){
            if(!f[a[i]]) ret++;//1~i-1 不能凑出 i，保留 i
            for(int j = a[i]; j <= a[n]; j++){
                f[j] = f[j] || f[j - a[i]];//用 || 一个满足即可
            }
        }
        cout << ret << endl;
    }
    return 0;
}

加油！志同道合的人会看到同一片风景。