【Codeforces 1108E1】Array and Segments (Easy version)

佚名 5年前 (2019-04-11) 随笔 1139人围观抢沙发百度已收录

题意

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

【题解】

枚举最大值和最小值在什么地方。
显然,只要包含最小值的区间,都让他减少。
因为就算那个区间包含最大值,也无所谓,因为不会让答案变小。
但是那些不包含最大值的区间却能让差值变大。
所以没有问题。

【代码】

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 300;

int n,m;
int a[N+10],segl[N+10],segr[N+10];
int cnt[N+10],idxi;

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for (int i = 1;i <= m;i++){
        cin >> segl[i] >> segr[i];
    }
    int ans = 0,anscnt=0;
    for (int i = 1;i <= n;i++)//a[i]最大
        for (int j = 1;j <= n;j++){//a[j]最小
            int x = a[i],y = a[j];
            int cnt = 0;
            for (int l = 1;l <= m;l++){
                if (segl[l]<=j && j <= segr[l]){
                    cnt++;
                    y--;
                    if (segl[l]<=i && i <= segr[l]){
                        x--;
                    }
                }
            }
            if (x-y>ans){
                ans = x-y;
                idxi = j;
                anscnt = cnt;
            }
        }
    cout<<ans<<endl;
    cout<<anscnt<<endl;
    for (int l = 1;l <= m;l++){
        if (segl[l]<=idxi && idxi<=segr[l]){
            cout<<l<<" ";
        }
    }
    return 0;
}