20/04/03

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

슬라이딩~ 윈도우

덱 안에 새로운 값을 push_back할때 넣기전 back값이 넣으려는값 이하이면 빼준다!

넣으려는 값을 A라고하고 맨뒤에 있는 값을 B라고 하면 A와 B가 같이 있을때 B를 선택할 경우에 항상 A를 선택하면 되기 때문이다. 따라서 모든 값을 deque에 넣었다 빼면 됨으로 O(N)으로 된다.

deque<pii> dq;
vector<int> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int a, b;
    cin >> a >> b;
    for (int i = 0; i < a; i++) {
        int tem;
        cin >> tem;
        v.push_back(tem);
    }
    for (int i = 0; i < a; i++) {
        while (!dq.empty() && dq.back().first >= v[i]) {
            dq.pop_back();
        }
        dq.push_back({ v[i],i });
        if (dq.front().second == i - b)
            dq.pop_front();
        cout << dq.front().first << ' ';
    }
}

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

vector<int> v;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int a, b;
    cin >> a >> b;
    for (int i = 0; i < a; i++) {
        int tem;
        cin >> tem;
        v.push_back(tem);
    }
    int ans = 0;
    int tem = 0;
    int l = 0, r = 0;
    for (int i = 0; i < a; i++) {
        tem += v[i];
        while (tem > b) {
            tem -= v[l];
            l++;
        }
        if (tem == b)ans++;
    }
    cout << ans;
}

입력받으면서 바로 처리해도 됨

 

 

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

bool che[MAXN];
vector<int> v;
void arra(int a) {
    for (int i = 2; i <= sqrt(a); i++) {
        if (che[i]) continue;
        for (int j = 2 * i; j <= a; j += i) {
            che[j] = 1;
        }
    }
    for (int i = 2; i <= a; i++) {
        if (che[i] == 0) v.push_back(i);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a;
    cin >> a;
    arra(a);
    int l = 0;
    int ans = 0;
    int tem = 0;
    for (int i = 0; i < v.size(); i++) {
        tem += v[i];
        while (tem > a) {
            tem -= v[l];
            l++;
        }
        if (tem == a)
            ans++;
    }
    cout << ans << '\n';
}

윗 문제에 아리스토 텔리스의 체 를 추가하면 됨 

 

https://www.acmicpc.net/problem/1806

1806번: 부분합

const int MAXN = 100005;
 
int arr[MAXN];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    int sum = 0, ans = 1000040,l = 0;
    for (int i = 0; i < a; i++) {
        cin >> arr[i];
        sum += arr[i];
        while (sum >= b) {
            ans = min(ans, i - l + 1);
            sum -= arr[l];
            l++;
        }
    }
    if (ans == 1000040) cout << 0;
    else cout << ans;
}

조건 부분을 살짝 바꾸면됨

 

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

#include<iostream>
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    int ans = 2000000000;
    for (int i = 0; i < a; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + a);
    int l = 0;
    for (int i = 0; i < a; i++) {
        while (arr[i] - arr[l] >= b) {
            ans = min(ans, arr[i] - arr[l]);
            l++;
        }
    }
    cout << ans;
}

똑 같 다

 

https://www.acmicpc.net/problem/1484

1484번: 다이어트

const int MAXN =50006;
 
int arr[MAXN];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int a;
    cin >> a;
    for (int i = 1; i < MAXN; i++) {
        arr[i] =  i * i;
    }
    int l = 1;
    vector<int> v;
    for (int i = 1; i < MAXN; i++) {
        while (arr[i] - arr[l] > a) {
            l++;
        }
        if (arr[i] - arr[l] == a) v.push_back(i);
    }
    if (v.empty())cout << -1;
    else {
        for (int a : v)
            cout << a << "\n";
    }
}

MAXN을 100'000까지 다 안봐도 된다 i^2- (i-1)^2 = 2*i-1이기 때문!

비슷 하다