[20/07/05] H. 표절 (2428)

 

처음에 정렬한 뒤 자신의 뒤에 있는 숫자만 0.9 이상인지 비교하면 될 줄 알았다. 하지만 그러면 90 95 100과 같은 값은 체크하지 못한다. 그래서 90퍼 이상인 범위를 투포인터로 잡아서 개수를 세었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool desc(int a, int b){ return a > b; };

int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
        
    sort(v.begin(), v.end(), desc);
    
    int r = 1;
    i64 ans = 0;

    for (int l = 0; l < n; l++)
    {
        r = max(l+1, r);
        while (r < n && v[l]*0.9 <= v[r])
            r++;
        
        ans += r - l - 1;
    }
    
    cout << ans;
    
    return 0;
}