글 읽기 - 철도문제입니다.

khseob0715 7년 전 0

stl sort에 대해서 공부를 이제 막 시작했습니다.

9-15의 cmp 구현이

y를 먼저 오름차순으로 정렬하고

y가 같다면 x도 오름차순으로 정렬하게 했습니다.

이렇게 구현하는게 맞는건가요?

그리고 답을 아래와 같이 처음 x의 값을 저장해서 포함하는지를 계산하였는데

잘못 생각한 부분이 있나요??

#include<stdio.h>
#include<vector>
#include<algorithm>
#define swap(x,y) {int t = x; x = y; y = t;}
using namespace std;
struct m{
	int x,y;
};
bool cmp(const m &u, const m &v){
	if(u.y == v.y){
		return u.x < u.x;
	}else{
		return u.y < v.y;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	vector<m> a(n);
	for(int i = 0 ; i < n ; i++){
		scanf("%d %d",&a[i].x,&a[i].y);
		if(a[i].x > a[i].y)
			swap(a[i].x,a[i].y);
	}
	int len;
	scanf("%d",&len);
	sort(a.begin(),a.end(),cmp);
	int first = a[0].x;
	int max = 0;
	int ct = 0;
	for(int i = 0 ; i < a.size(); i++){
	//	printf("%d %d\n",a[i].x,a[i].y);
		if(a[i].x >= first && a[i].y <= first + len){
			ct++;
			if(max < ct){
				max = ct;
			}
		}else{
			first = a[i].x;
			ct = 0;
			if(a[i].x >= first && a[i].y <= first + len){
				ct++;
			}
	//		printf("fi %d\n",first);
		}
	}
	printf("%d\n",max);

}

chogahui05 7년 전 1

전 내공이 얕아서, qsort + priority Queue를 이용했습니다.

sorting만으로 풀기는 제 머리가 딸려서시리.. 우선 순위 큐 이용하니까 쉽게 풀리더라고요.

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

문제

문제

출처

ICPC

철도문제입니다.

khseob0715 7년 전 0

chogahui05 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말