[Codeforces 1108E1] Array and Segments (Easy version)

[Codeforces 1108E1] Array and Segments (Easy version) - 1800

문제 설명 : 

n개의 숫자와 q개의 쿼리(구간)가 주어진다. 각 쿼리는 시작점~끝점으로 표현되며 그 쿼리를 '적용'한다면 시작점~끝점에 해당하는 인덱스의 배열의 값을 모두 1씩 감소시킨다. 여기서 0개 이상의 쿼리를 적용하여 나온 결과 배열에서 가장 큰 값과 가장 작은 값의 차이를 최대가 되도록 만드는 문제이다.

풀이 : 

내가 생각해야 할 것은 '어떤 수를 배열에서 가장 큰 값이 되도록 할 것인가'이다. 만약 i번째 수를 가장 큰 값이 되도록 정했다면 그 값은 그대로 고정시키고 다른 값을 빼준다. 즉 쿼리 중에서 i를 포함하지 않는 구간만 적용하여 값을 빼주는 것이다. 어차피 특정 구간 안에 최대값과 최소값이 모두 포함되어 있다면 둘 다 1을 빼주나 안 빼주나 차이는 동일하기 때문이다.

주의할 점 : 

-

배운 점 : 

-

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 309;
const int INF=1<<29;
 
int arr[SIZE];
pii seg[SIZE];
 
int main(){
    int n,q;    scanf("%d %d",&n,&q);
 
    int maxi=-INF,mini=INF;
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        maxi=max(maxi,arr[i]);
        mini=min(mini,arr[i]);
    }
 
    for(int i=1 ; i<=q ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        seg[i]={a,b};
    }
    int max_sum=maxi-mini;
    vector<int> ans;
 
    for(int i=1 ; i<=n ; i++){
        vector<int> select;
        int sub[SIZE]={0};
 
        for(int j=1 ; j<=q ; j++){
            if(i>=seg[j].first && i<=seg[j].second); //do nothing
            else{
                select.push_back(j);
                for(int k=seg[j].first ; k<=seg[j].second  ; k++)
                    sub[k]--;
            }
        }
 
        int max_cnt=-INF,min_cnt=INF;
        for(int j=1 ; j<=n ; j++){      
            max_cnt=max(max_cnt,arr[j]+sub[j]);
            min_cnt=min(min_cnt,arr[j]+sub[j]);
        }
 
        int cur_sum=max_cnt-min_cnt;
        if(cur_sum>max_sum){
            max_sum=cur_sum;
            ans=select;
        }
    }
    printf("%d\n",max_sum);
    printf("%d\n",ans.size());
    showAll(ans,SPACE);
 
    return 0;
}