Jerrlee's blog

Jerrlee's blog

CF1680A 题解

posted on 2022-05-15 14:40:29 | under 题解 |

题意

如果满足以下两个条件,则数组是美丽的:

  • 数组中至少有 $l_1$ 并且最多有 $r_1$ 个值等于数组所有值的最小值;

  • 数组中至少有 $l_2$ 并且最多有 $r_2$ 个值等于数组所有值的最大值。

求这个数组内包含的元素数量的最小值。

思路

观察样例,发现当 $l_1 \sim r_1$ 与 $l_2 \sim r_2$ 有共同的数时,选择 $l_1$ 和 $r_1$ 的最大值即可(最大值此时也是最小值)。

当 $l_1 \sim r_1$ 与 $l_2 \sim r_2$ 无共同的数时,既要满足最小值的数量要求,也要满足最大值的数量要求,那数组不仅包括 $l_1$ 个最小值,还得包括 $l_2$ 个最大值,答案就是 $l_1+l_2$。

代码

#include<iostream>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a>=c&&a<=d) cout<<a;
        else if(c>=a&&c<=b) cout<<c;
        else cout<<a+c;
        cout<<endl;
    }
}

AC 记录(洛谷)

AC 记录(CF)