글 읽기 - 죄송하지만 2532 먹이사슬 다시 질문 좀..

mrcamel 6년 전 0

저번엔 스택으로 답이 안나오길레

이리저리 생각해보다가 '최장 감소 수열'을 생각해봤습니다

끝나는 부분을 오름차순으로 정렬하고 시작 부분에서 최장 감소 수열 찾기로 하고

'최장 증가 수열'로 만들기 위해 시작부분을 1e9(최대값) - 시작부분 으로 바꾸었습니다

예제의 경우

7 3 4

1 2 4

3 1 5

4 7 8

5 5 7

6 9 10

2 6 10

999,999,997 4 <

999,999,998 4 <

999,999,999 5 <

999,999,993 8

999,999,995 7

999,999,994 10

999,999,991 10

저번에 yukariko님이 주신 케이스

4 3 4

5 2 5

2 0 5

3 3 10

1 0 10

999,999,997 4 <

999,999,998 5 <

1,000,000,000 5 <

999,999,997 10

1,000,000,000 10 <

yukariko님이 주신 케이스와 같은 경우도 이제 잘 나오는거 같은데

또 다른 경우가 있을까요?

#include <iostream>
#include <cstdio>
#include <fstream>
#include <deque>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

#define in cin
#define out cout
#define PII pair<int, int>

int cmp(const PII &a, const PII &b)
{
    if(a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}

int main()
{
    int n; scanf("%d", &n);
    vector< PII > v;
    for(int i=0; i<n; i++)
    {
        int i1, i2, i3; scanf("%d %d %d", &i1, &i2, &i3);
        v.push_back(make_pair(1e9-i2, i3));
    } sort(v.begin(), v.end(), cmp);

    for(int i=1; i<n; i++)
    {
        if(v[i].first == v[i-1].first &&
           v[i].second == v[i-1].second)
        {
            v[i-1].first = -1;
        }
    }


    int q[500001];
    int qsize = 1;
    q[1]=v[0].first;

    for(int i=2; i<=n; i++)
    {
        if(v[i-1].first == -1) continue;
        if(q[qsize] <= v[i-1].first)
        {
            qsize++;
            q[qsize] = v[i-1].first;
        }
        else
        {
            int t = lower_bound(q+1, q+qsize+1, v[i-1].first) - q;
            q[t] = v[i-1].first;
        }


   }

    out << qsize << endl;
    return 0;
}

yukariko 6년 전 0

저도 LIS 를 이용해서 구현해줬는데 자꾸 틀림이 뜨더라구요..

이 알고리즘을 쓰는게 맞는지 저도 궁금하네요

pl0892029 6년 전 2

dovelet.com 에서 채점해보세요. 반례데이터를 볼수 있으니 ^_^

mrcamel 6년 전 1

반례데이터의 n이 500,000이네요;

답과 차이는 2나는데 뭐가 잘못됬는지 감이 안잡혀요 ㅠㅠ

mrcamel 6년 전 0

덕분에 AC 받았어요ㅎㅎ

제가 lower bound 함수를 잘못 이해하고 있었네요;

감사합니다 추석에 복 많이 받을실꺼에요!

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

문제

문제

출처

ICPC

죄송하지만 2532 먹이사슬 다시 질문 좀..

mrcamel 6년 전 0

yukariko 6년 전 0

pl0892029 6년 전 2

mrcamel 6년 전 1

mrcamel 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말