BOJ 2428 ) 표절 (C++)

2428번: 표절

 N이 10^6이므로 쌍을 찾기 위해 이중 for문을 돌릴 경우 시간초과가 난다. binary search를 써야하고 (i,j)와 (j,i)는 같은 케이스 이므로 i<j인 경우의 개수만 세서 정답에 더해준다. 

 오름차순 정렬을 하면 0.9*size(i)를 초과하는 부분부터는 볼 필요가 없다. 그러므로 0.9size(i)이하인 j중 가장 큰 j를 찾는다. isPossible이 참인 경우 mid<=j인 상태이므로 위쪽 절반을, 거짓인 경우 mid > j이므로 아래쪽 절반을 검토한다. 가장 큰 인덱스가 j인 경우 (v[i], ?)꼴의 쌍의 개수는 j-i개 이므로 정답에다가 j-i만큼을 더해준다. 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int N;
vector<ll> v;
ll ans =0;

bool isPossible(int idx, int n){
    return v[idx]>=0.9*v[n];
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>N; int t;
    for(int i=0;i<N;i++){
        cin>>t;
        v.push_back(t);
    }
    sort(v.begin(), v.end());

    int mid, low, high, ansidx;
    for(int i=0;i<N-1;i++){
        low = i;
        high =  N-1;
        ansidx = i;
        while(low<=high){
            mid = (low+high)/2;
            if(isPossible(i, mid)){
                ansidx = max(mid, ansidx);
                low = mid+1;
            } else {
                high = mid - 1;
            }
        }
        ans += ansidx - i;
    }
    cout<<ans;
    return 0;
}