B. Vika and Squares

implementation, math

출처: Codeforces B. Vika and Squares

SOL)
최소값을 찾을때마다 index를 set에 추가한다.
추가로 idx + n도 추가한다.
i + n을 넣어주는 이유는 환형큐 처럼 보기 어려워서 어디 까지
갈수 있는지 편하게 찾기 위해서 넣은 것이다.

예를 들어 2 4 2 3 3이 인풋일때
set = {0, 2, 5, 7}이 들어간다.
i = 0 부터 i = n-1일까지 하나씩 lower_bound를 찾는데

i = 1일때 *it = 2가 나온다.
이 말은 4가 index 2까지 갈수 있다는 소리다.

i = 4일때는 *it = 5 즉, arr[4] = 3은 arr[0] = 2까지 갈 수 있다는 소리다.

i + n을 넣어주는게 참 좋은 생각인거 같다.



[-] Collapse

#include<stdio.h>
#include<algorithm>
#include<set>

using namespace std;
typedef long long ll;

const int N = 400000;
int arr[N];
int n;
set<int> ms;
int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    int mn = 1000000010;
    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
        if (mn > arr[i]) mn = arr[i];
    }

    for (int i = 0; i < n; i++){
        if (arr[i] == mn){
            ms.insert(i);
            ms.insert(i + n);
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++){
        set<int>::iterator it = ms.lower_bound(i);
        ans = max(ans, 0LL + *it - i);
    }
    printf("%I64d", ans + (ll)mn*n);
    return 0;
}