1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #include <stdio.h>int check[100000]={0}; //지연수=불가능 -1=위치int height[100000]={0};int num[100000]={0};int answer[100000]={0};void line_height(int n); //키가 작은 순서대로 정렬void line_people(int n); //사람들의 순서//int where_num(int n, int a); //그 사람의 위치//void check_no(int n); //위치가 정해진 키는 더이상 다른 위치에 올수 없으므로 불가능//void pr(int n);int main(void){ int n, i; //입력 시작 scanf(" %d", &n); //전체 사람의 수 for(i=0; i<n; i++) { scanf(" %d", &height[i]); //사람들의 키 } for(i=0; i<n; i++) { scanf(" %d", &num[i]); //자가 앞에 있는 사람들 중에서 자기보다 키가 작거나 같은 사람들의 수 } //입력 끝 line_height(n); //키가 작은 순서대로 정렬 line_people(n); //정답 출력 for(i=0; i<n; i++) { printf("%d\n", answer[i]); } return 0;}void line_height(int n){ int i, j, temp, min; for(i=0; i<(n-1); i++) { min=i; for(j=i+1; j<n; j++) { if(height[j]<height[min]) { min=j; } } if(min!=i) { temp=height[i]; height[i]=height[min]; height[min]=temp; } }}void line_people(int n){ int i, j, w, c, cnt=1; for(i=n-1; i>=0; i--) { if(i!=0) { c=0; for(j=0; c<num[i]; j++) { if(check[j]!=-1) { check[j]=cnt; //작은 순서대로 num[i]개 만큼 불가능 c++; } } c=0; for(j=n-1; c<(i-num[i]); j--) { if(check[j]!=-1) { check[j]=cnt; //큰 순서대로 (i-num[i])개 만큼 불가능 c++; } } } for(j=0; j<n; j++) { if(check[j]!=cnt && check[j]!=-1) //불가능 하지 않은 위치 { w=j; answer[i]=height[w]; check[w]=-1; break; } } //pr(n); //check_no(n); //pr(n); //printf("\n"); cnt++; }}/*int where_num(int n, int a){ int i; for(i=0; i<n; i++) { if(check[i]!=a && check[i]!=-1) return i; }}*//*void check_no(int n){ int i; for(i=0; i<n; i++) { if(check[i]==1) { check[i]=0; } }}*//*void pr(int n){ int i; for(i=0; i<n; i++) { printf("%d ", check[i]); } printf("\n");}*///뒤에서부터 배열//만약 작은 수가 4개라면 작은 순대로 4개 제외, 큰 순서재로 전체-4개 제외 |
2018.04.21 10:13
정올 - 알고리즘 - 줄세우기(2469) - Time Limit Exceed
조회 수 567 추천 수 0 댓글 0
