模拟赛题讲解[16]

来自 yukuai26 2022-08-07 noi.ac #2764

题目描述：

紫开始研究特殊的括号序列

这些特殊括号序列的形式是若干个右括号（可以没有）在前，若干个左括号（可以没有）在后。

比如 ((，)))，))( 都是特殊的括号序列

显然刚开始给出的特殊的括号序列都不合法。

紫决定把所有序列首尾相连（按照紫想要的顺序排列)，然后她再删除若干个括号，她希望最终删完括号的序列是一个合法的括号序列。

以下合法的括号序列定义

1、空串是一个合法的括号序列

2、若 $A,B$ 分别是合法的括号序列，则 $AB$ 是合法的括号序列

3、若 $A$ 是合法的括号序列，则 $(A)$ 是合法的括号序列

紫想要知道，她最少需要删除多少个括号。

输入格式：

第一行一个正整数 n，表示有多少个括号序列

接下来 n 行，每行两个非负整数 $a_{i},b_{i}$

$a_{i}$ 表示第 $i$ 个括号序列的右括号数，$b_{i}$ 表示第 $i$ 个括号序列的左括号数

输出格式：

一个整数表示最少需要删除多少个括号。

输入1：

3
1 3
2 2
1 1

输出1：

4

样例解释：

最优的方案之一最终序列是 )((( )( ))((

左右各删两个即可

最优方案并不唯一

数据规模与约定：

对于 $40\%$ 的数据，满足 $n\le 10$

对于 $60\%$ 的数据，满足 $n\le 20$

另存在 $20\%$ 数据，满足若 $a_{i}\le a_{j}$ 则 $b_{i}\ge b_{j}$

对于 $100\%$ 的数据，满足 $n\le 100000,0\le a_{i},b_{i}\le 10^9$

题解：

这里先放个巨佬在考场代码里写的（有删改） Orz

/*
升特殊的括号序列：a<b 
平特殊的括号序列：a=b 
降特殊的括号序列：a>b
最优解必然是：升升....升平....平平降降....降
而每次选择一定选升特殊的括号序列中a最小，
平特殊的括号序列随便，
降特殊的括号序列b最大(相当于反着操作) 
根据贪心模拟括号判定 
*/ 

好的，开始我们的讲解

首先，别搞错了，(是左括号，) 是右括号，给出的是这样的 ))((((

考虑贪心。假如把所有的括号序列按照 $a_i > b_i$ 或 $a_i \le b_i$ 进行分类

则第二类一定会放在第一类的前面，否则一定不优。

因为 $a_i > b_i$ 的会让未匹配的左括号变少

反之，在末尾加入一个第二类的，会使未匹配的左括号数增多

此时第一类中的右括号无法匹配这些增加的左括号，显然这不优。

然后我们就可以考虑同一类中的选哪个了

显然我们会想尽可能早匹配掉左括号

每次加入一个第二类的，一定会导致未被匹配的左括号数增加 $x (x\in \mathbb{N})$ 个

那么这个结论有什么用呢，别急，后面会用到。

比起寄希望于后面第一类的右括号来匹配他们，不如直接在第二类内匹配掉尽可能多的

或者说，我们要最小化第二类中的未匹配的左括号

这等价于要最大化第二类中的匹配的右括号

我们刚刚说了，左括号的数量是单调不降的

而右括号是有可能匹配失败的，因为它前面可能没有左括号跟它匹配

于是，我们对于第二类的，直接按右括号数量 $a_i$ 从小到大排序就好了

同理，我们把上面的推导颠倒过来，可以退出第一类的情况是按左括号的数量 $b_i$ 从大到小排序。

时间复杂度 $O(n \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,p1,p2,ans,now;
char s[N];
struct node{int l,r;}t1[N],t2[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<=n; i++)
    {
        cin >> u >> v;
        if(u>v) t2[++p2]={u,v};
        else t1[++p1]={u,v};
    }
    sort(t1+1,t1+1+p1,[](node a,node b){return a.l<b.l;});
    sort(t2+1,t2+1+p2,[](node a,node b){return a.r>b.r;});
    int now=0;
    for(int i=1; i<=p1; i++)
    {
        if(t1[i].l>now) ans+=t1[i].l-now;
        now-=min(t1[i].l,now);
        now+=t1[i].r;
    }
    for(int i=1; i<=p2; i++)
    {
        if(t2[i].l>now) ans+=t2[i].l-now;
        now-=min(t2[i].l,now);
        now+=t2[i].r;
    }
    cout << ans+now << '\n';
    return 0;
}