526互联

same

发布时间 2023-10-10 20:21:34作者: hsy2093

对某一区间进行相同操作的题目汇总(2023.1.17)

通常来说，线段树是处理题目类似于“能够对某一区间进行相同操作”的数据结构。但很多时候，当题目设定足够简洁时，能够通过求前缀、贪心等方法来更快速地解决问题。本文通过以下两道题目展开说明。

题一： [USACO21DEC] Air Cownditioning B

题目描述

Farmer John 的 $N$ 头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些，而有些奶牛则喜欢温度高一些。

Farmer John 的牛棚包含一排 $N$ 个牛栏，编号为 $1 \ldots N$，每个牛栏里有一头牛。 第 $i$ 头奶牛希望她的牛栏中的温度是 $p_i$，而现在她的牛栏中的温度是 $t_i$。为了确保每头奶牛都感到舒适，Farmer John 安装了一个新的空调系统。该系统进行控制的方式非常有趣，他可以向系统发送命令，告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 $5 \ldots 8$ 的温度升高 1 个单位」。一组连续的牛栏最短可以仅包含一个牛栏。

请帮助 Farmer John 求出他需要向新的空调系统发送的命令的最小数量，使得每头奶牛的牛栏都处于其中的奶牛的理想温度。

样例输入
5
1 5 3 3 4
1 2 2 2 1

样例输出
5

写题思路

  1. 题目给了当前序列与目标序列，可以先处理题目数据，通过求对应位置差值生成新数组temp[ ]，从而将问题转换成通过多少次操作能够使cha数组的所有元素值都为0。
  2. 对于样例来说，temp = [0, 3, 1, 1, 3]
    如果需要对同一区间进行加一或者减一的操作，则需要对该区间内所有数都处理，听上去有点儿麻烦。这时候想起来了之前学的求前缀差的差值能够仅修改区间前后两个的值，该操作就方便了很多，所以考虑对temp数组再次处理，得到cha = [0, 3, -2, 0, 2, -3]
    在这一步骤中，需要注意的地方是要在原来的temp序列前后都补上0，不然可能会导致前后的数据处理不到。
  3. 回到题目给的两种操作。
    此时区间内升高一度，等价于区间第一个元素值+1， 最后一个元素值-1。区间降低一度，反之。
    由于题目要求最小的指令次数。可得不存在先把cha数组中的正数变成负数，再变成0。所以思路为找到一个正数，再找到一个负数，一个加一，一个减一。如果最后正数的值多了，或者负数的值多了，那就单独对这个区间操作。
  4. 上一点所说的操作等价于分别求cha数组中正数和与负数和，比较二者绝对值大小。ans=绝对值小的和+二者绝对值相减多出来的和。这里第一项就对应于能够通过一个操作改变两个值。第二项则是对多出来的数单独操作。

代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int p[100005];
int t[100005];
int temp[100005];
int cha[100005];

int main(){
    int n, ans = 0;
    int sum_z = 0, sum_f = 0;
    cin >> n;
    for(int i = 1; i <= n; i++)   cin >> p[i];
    for(int i = 1; i <= n; i++){
        cin >> t[i];
        temp[i] = p[i] - t[i];
        cha[i] = temp[i] - temp[i-1];
    }
    cha[0] = 0;
    cha[n+1] = 0 - temp[n];
    for(int i = 0; i <= n+1; i++){
        if(cha[i] > 0)
            sum_z += cha[i];
        if(cha[i] < 0)
            sum_f -= cha[i];
    }
    if(sum_z > sum_f)
        ans = sum_f + (sum_z - sum_f);
    else
        ans = sum_z + (sum_f - sum_z);
    cout << ans << endl;
    return 0;
}

题二 「USACO 2022 January Contest, Bronze」Drought

题目描述

Farmer John 的草地里的草在一场大旱中都干死了。经过数小时的绝望和沉思，Farmer John 想到了一个绝妙的主意，购买玉米来喂养他宝贵的奶牛。
FJ 的 $N$ 头奶牛 $（1\leq N\leq 10^5）$ 排成一行，队伍中的第 $i$ 头奶牛的饥饿度为 $hi（0\leq hi\leq 10^9）$ 。由于奶牛是社会性动物，她们坚持一起进食，FJ 降低奶牛饥饿度的唯一方法是选择两头相邻的奶牛 $i$ 和 $i+1$ 并分别喂她们一袋玉米，令她们的饥饿度各减少 $1$。

FJ 想将他的奶牛喂至所有的奶牛都具有相同的非负饥饿度。请帮助 FJ 求出他喂奶牛达到上述状态所需的最少玉米袋数，或者如果不可能达到，输出 $−1$ 。
样例输入
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9
样例输出
14
16
-1
-1
-1

写题思路

  1. 读题，题目中一次操作的作用为：选中相邻的两只奶牛，从而各降低饥饿值1。最后希望所有的奶牛都降低到饥饿度相同。
  2. 先考虑特殊情况。可以发现，如果第一头奶牛的值要变化，那么必然是喂第一二头奶牛，最后一头奶牛同理。所以能够达到题目目标，首先需要满足的条件为第一头奶牛的饥饿值要小于第二头，最后一头奶牛的饥饿值要小于倒数第二头。
  3. 因为可以选中相邻两只奶牛进行操作，绑定分组的情况下，中间的奶牛会重叠在两个分组间，从而相互影响，所以不考虑这个思路。又因为在遍历的过程中，希望经过操作后，前后两头奶牛的饥饿值能尽可能接近。所以可以用贪心的算法来实现。
  4. 贪心具体实现过程如下
    1） 先从前往后扫一遍奶牛，如果当前奶牛的饥饿值大于前一头奶牛，那么就喂当前奶牛和下一头奶牛，直到当前奶牛的饥饿值等于前一头奶牛。这样扫完一遍后，奶牛的饥饿值从左往右将会依次递减。而这时，如果答案有解的话，最后一头奶牛的饥饿值就是可能的答案ans。因为这个值代表了最大的“所有奶牛相同饥饿值”。这个值越大，题目所要求的喂的次数就越少。
    2）扫的第一遍无法满足题目要求。所以要扫第二遍，第二遍在已知可能答案的情况下，就能模拟流程。但是其中可能存在将奶牛喂到负饥饿值的情况。所以扫完后最后核对一遍扫的末尾饥饿值与可能答案ans，如果二者相等，则验证该方案可行，并且最小投喂次数等于sum - ans * n。

代码

#include <stdio.h>
#include <iostream>
typedef long long ll;
#define maxn 100005
using namespace std;
ll h[maxn];
ll sum;
int n;

ll work(){
    ll ans = 0;
    ll t = 0;
    if(n == 1)
        return 0;
    if(h[1] > h[2] || h[n-1] < h[n])
        return -1;
    //从前往后扫一遍
    for(int i = 1; i < n; i++){
        h[i] -= t;
        h[i+1] -= t;
        if(h[i] < 0)
            return -1;
        if(h[i+1] - h[i] > 0)
            t = h[i+1] - h[i];
        else  t = 0;
    }
    ans = h[n];
    if(ans < 0)
        return -1;
    //找到答案后再扫一遍
    for(int i = 1; i < n; i++){
        t = h[i] - ans;
        h[i+1] -= t;
    }
    if(ans == h[n])
        return sum - ans * n;
    else return -1;
}

int main(){
    int t;
    cin >> t;
    for(int i = 0; i < t; i++){
        cin >> n;
        sum = 0;
        for(int i = 1; i <= n; i++){
            cin >> h[i];
            sum += h[i];
        }
        cout << work() << endl;
    }
    return 0;
}