706-B, *1100

Problem - 706B - Codeforces

문제

• $n(1 \leq n \leq 10^{5})$개의 가게에서 어떤 음료수를 판다
• $q(1 \leq q \leq 10^{5})$번, $m_{i}$원이 있을 때 최대 몇 개의 가게에서 그 음료를 살 수 있는지(!) 출력한다
• ! 은 $O(log \ n)$으로 동작해야 한다. 그러면 알고리즘이 $O(qlog \ n)$으로 동작하게 된다

 

$O(nlog\ n)$

각 가게에서의 음료 가격을 오름차순으로 정렬하여 $O(nlog\ n)$
$q$번 이진탐색으로 $m_{i}$가 몇 번째에 위치하는지 구한다 $O(qlog\ n)$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
vector<int> shop;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    int tmp;
    while(n--){
        cin >> tmp;
        shop.push_back(tmp);
    }
    sort(shop.begin(), shop.end());
 
    int q;
    cin >> q;
    int able;
 
    int minval = shop[0];
    int maxval = shop[shop.size()-1];
 
    while(q--){
        cin >> able;
        if(able < minval) cout << 0 << endl;
        else if(able >= maxval) cout << shop.size() << endl;
        else cout << upper_bound(shop.begin(), shop.end(), able) - shop.begin() << endl;
    }
 
    return 0;
}cs

$O(n+q)$

$DP_{m}$을 $m$원으로 이용할 수 있는 가게의 수라고 하자. 그러면
$$DP_{m} = DP_{m-1} + \mathrm{(The\ number\ of\ stores\ sell\ juice\ for\ price\ m)}$$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int index_price_store_num[100001] {};
long long prefix_sum[100001] {};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n;
    cin >> n;
    int tmp;
    int maxprice = 0;
    for(int i = 0; i < n; i++){
        cin >> tmp;
        maxprice = max(maxprice, tmp);
        index_price_store_num[tmp]++;
    }
 
    for(int i = 1; i <= maxprice; i++) prefix_sum[i] = prefix_sum[i-1] + index_price_store_num[i];
 
    int q;
    cin >> q;
    while(q--){
        cin >> tmp;
        if(tmp > maxprice) cout << n << endl;
        else cout << prefix_sum[tmp] << endl;
    }
 
    return 0;
}cs