[Codeforces Round 1000(Div.2)] B. Subsequence Update

https://codeforces.com/contest/2063/problem/B

Codeforces Round 1000(Div.2) - B. Subsequence Update

문제 유형: 정렬, 그리디

시간 제한: 1.5초

메모리 제한: 256MB

 

문제

You are given an integer sequence a1,a2,…,an, and a segment [l,r] (1≤l≤r≤n).

You must perform the following operation on the sequence exactly once.

• Choose any subsequence of the sequence a, and reverse it. Note that the subsequence does not have to be contiguous.

Formally, choose any number of indices i1,i2,…,ik

such that 1≤i1<i2<…<ik≤n. Then, change the ix-th element to the original value of the ik−x+1-th element simultaneously for all 1≤x≤k.

Find the minimum value of al+al+1+…+ar−1+ar after performing the operation.

 

정수 수열 a1, a2, ..., an과 세그먼트 [l, r]을 받는다.

당신은 다음의 연산을 정확히 한 번 적용해야 한다.

• 임의의 인덱스들을 골라서, subsequence를 구성한다. 그 뒤, subsequence의 요소들끼리 reverse한다.

연산 이후의 a수열의 [l, r]구간의 총합의 최소값을 구하시오.

 

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.

The first line of each test case contains three integers n, l, r (1≤l≤r≤n≤10^5) — the length of a, and the segment [l,r].

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9).

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

 

첫째 줄에 테스트케이스의 수 t가 주어진다.

각 테스트케이스의 첫 줄에는 n, l, r이 주어진다.

두 번째줄에는 a의 요소들인 n개의 정수들이 주어진다.

 

출력

For each test case, output the minimum value of al+al+1+…+ar−1+ar on a separate line.

각 테스트케이스 별로 연산을 적용한 a수열의 [l, r]구간의 총합의 최소값을 구하시오.

 

풀이

편의상 0-indexed로 변환했다.

자, i < l, j > r인 두 인덱스 i, j간에 교환하는 것은 의미가 있을까? 당연히 아니다.

이 말의 의미는, 리버스시킬 부분수열의 범위를 [0, r], 또는 [l, n-1]으로 잡아야 한다는 것이다. 이 두 가지 뿐이다. (0-indexed로 변환했음을 유의하자.)

몇 개를 어떻게 뒤집을 것인지에 대한 세부사항을 구할 필요는 없다. 최소 총합만 알면 되니말이다.

[0, r]구간과 [l, n]구간에서 가장 작은 정수 r-l+1개를 골라서 더한 누적합 두 가지 중에서 더 작은 숫자를 골라서 출력하면 된다.

 

요소들 각각의 크기가 크므로, 오버플로우에 유의하자. 총합은 64비트정수여야 감당가능하다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve() {
  int n, l, r;
  cin >> n >> l >> r;
  l--;
  r--;

  vector<int> arr(n);
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  auto arr1 = arr;
  auto arr2 = arr1;

  int m = r - l + 1;
  sort(arr1.begin(), arr1.begin() + r + 1);
  sort(arr2.begin() + l, arr2.end());

  ll a = 0;
  for (int i = 0; i < m; ++i) {
    a += arr1[i];
  }

  ll b = 0;
  for (int i = l; i < m + l; ++i) {
    b += arr2[i];
  }

  cout << min(a, b) << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--)
    solve();
  return 0;
}