글 읽기 - [알고리즘 구현이 제대로 되었는지 궁금합니다.]

joqjoq966 3년 전 0

제가 생각한 알고리즘은 다음과 같습니다.

a+b의 값을 모두 저장한 배열 == arr1, c+d의 모든 값을 저장한 배열 ==arr2

arr2를 sort합니다.

arr1의 첫번째 원소부터 arr2의 mid와 더해서 0보다 큰지 작은지 같은지를 이용하여 같을 때 같은 갯수가 총 몇개인지를 구해서 cnt에 더해줍니다.

이렇게 생각하고 구현했는데 잘못 생각한 것일까요? 아니면 구현이 잘못 된 것일까요?

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int a[4001];
int b[4001];
int c[4001];
int d[4001];

int arr1[16000001];
int arr2[16000001];

bool cmp(long long x, long long y) {
    return x>=y;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>N;
    for(int i=0;i<N;++i) {
        int x, y, z, w;
        cin>>x>>y>>z>>w;
        a[i]=x; b[i]=y; c[i]=z; d[i]=w;
    }
    int x=0;
    for(int i=0;i<N;++i) {
        for(int j=0;j<N;++j) {
            arr1[x]=(a[i]+b[j]);
            arr2[x]=(c[i]+d[j]);
            x++;
        }
    }
    x = N*N;
    sort(arr2,arr2+x);
    
    int lo = 0;
    int hi = x-1;
    long long cnt =0;
    for(int i=0;i<x;i++) {
        while(lo<hi) {
            long long mid = (lo+hi)/2;
            if(arr1[i]+arr2[mid]>0) {
                hi = mid -1;
            }
            else if(arr1[i]+arr2[mid]<0) {
                lo = mid +1;
            }
            else {
                int lo_idx=0;
                int hi_idx=0;
                int temp = mid;
                while(arr2[mid]==arr2[mid-1] && mid>=0) {
                    mid--;
                }
                lo_idx = mid;
                mid = temp;
                while(arr2[mid]==arr2[mid+1] && mid<x) {
                    mid++;
                }
                hi_idx = mid;
                cnt+=(hi_idx-lo_idx+1);
                mid=temp;
                break;
            }
        }
    }
   
    cout<<cnt<<endl;
}

3587jjh 3년 전 0

반례입니다

0 0 0 0

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[알고리즘 구현이 제대로 되었는지 궁금합니다.]

joqjoq966 3년 전 0

3587jjh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말