贪心专题练习

牛牛学括号

题目要求

• 每次操作必须删除一个左括号和一个右括号，且删除后序列仍需合法。
• 合法的括号序列要求每个右括号之前必须有对应的左括号。

分析

输入的都是合法的括号，即左括号=右括号，可利用这一点去解题

注意：

• 中间取模是必要的，防止计算过程中溢出。
• 中间取模不影响结果正确性，因为模运算的性质保证了分步取模与最终取模等价。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int c=0;
    long long ans=1;//记录方法总数，初始化答案为1
    int m=1e9+7; //模数，防止答案溢出
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') c++;//记录当前左括号的数量
        else{
            ans*=c; //此时，遇到了右括号，说明不能继续往后遍历，要开始为左括号匹配了
            c--; //刚才遍历了几个左括号，就说明后面有几个右括号与之匹配
            ans%=m; //分段相乘，匹配完一个，左括号数量减一
        }
    }
    cout<<ans; //要在中间对ans取模，避免溢出
    return 0;
}

牛牛的朋友

题目要求

每只牛必须移动 X 个单位（向左或向右），目标是使移动后最左和最右牛的距离最小。

分析

牛群有两种移动方向（这里只分析最优策略）

1. 同向移动
2. 双向移动

对于双向移动，我们需要将牛群分成两部分：

• 前 i-1 头牛：全部向右移动 +X。
• 后 n-i+1 头牛：全部向左移动 -X。

我们需要计算这种分组下，移动后牛群的最左位置和最右位置。如图所示：

注意

并不是所有情况下 maxp-minp 都会比初始值 res 小，一般情况下分割成两部分双向移动最左端和最右端距离会更近，但有时同向移动比双向移动更近，通向移动后左右两端的距离不变，因此，在这里用初始时两端的距离来初始化res，如果采用分割的方式，会出现比res更小的值，则更新，否则就说明此时，同向更优，无需更新。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long a[n];
    for(int i=0;i<n;i++) cin>>a[i];//存储牛位置
    int x;
    cin>>x;
    int max1=-1e8,min1=1e8;
    for(int i=0;i<n;i++){
        if(a[i]>max1)max1=a[i];//先求出牛初始位置的最大距离，目的是用来初始化res,同时包含
        if(a[i]<min1)min1=a[i];//同向移动的情况
    }
    int res=0;
    res=max1-min1;
    sort(a,a+n);
    // 枚举分割点i，将前i-1头牛向右移动，其余向左移动
    for(int i=1;i<n;i++){  //数组是从0开始索引，但要分割成两半部分，所以从1开始
        int max2=max(a[n-1]-x,a[i-1]+x);//求最右边两种情况的max
        int min1=min(a[0]+x,a[i]-x);//求最左边两种情况的min
        if(res>max2-min1){
            res=max2-min1;//更新res
        }
    }
    cout<<res;
    return 0;
}