2011-08-28 07:19:39Morris
d731. 11039 - Building designing
d731. 11039 - Building designing
作法 : Greedy
分兩堆做好, 排序結束後, 從兩個陣列中交錯拿出符合且最大的數字
/**********************************************************************************/
/* Problem: d731 "11039 - Building designing" from UVa ACM 11039 */
/* Language: C */
/* Result: AC (196ms, 4236KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 20:01:41 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int A[500000], B[500000];
int cmp(const void *a, const void *b) {
int *aa, *bb;
aa = (int *)a, bb = (int *)b;
return *aa < *bb;
}
main() {
int t, n, x, a;
scanf("%d", &t);
while(scanf("%d", &n) == 1) {
int Aidx = 0, Bidx = 0;
for(a = 0; a < n; a++) {
scanf("%d", &x);
if(x > 0) A[Aidx++] = x;
else B[Bidx++] = -x;
}
qsort(A, Aidx, sizeof(int), cmp);
qsort(B, Bidx, sizeof(int), cmp);
int in1 = 0, in2 = 0, last = oo, flag = 0;
int tmp = 0, Ans = 0;
while(in1 <= Aidx && in2 <= Bidx) {
if(!flag) {
while(A[in1] > last && in1 < Aidx) in1++;
if(in1 == Aidx) break;
last = A[in1], in1++;
} else {
while(B[in2] > last && in2 < Bidx) in2++;
if(in2 == Bidx) break;
last = B[in2], in2++;
}
tmp++, flag = 1-flag;
}
Ans = Ans > tmp ? Ans : tmp;
in1 = 0, in2 = 0, last = oo, flag = 1, tmp = 0;
while(in1 <= Aidx && in2 <= Bidx) {
if(!flag) {
while(A[in1] > last && in1 < Aidx) in1++;
if(in1 == Aidx) break;
last = A[in1], in1++;
} else {
while(B[in2] > last && in2 < Bidx) in2++;
if(in2 == Bidx) break;
last = B[in2], in2++;
}
tmp++, flag = 1-flag;
}
Ans = Ans > tmp ? Ans : tmp;
printf("%d\n", Ans);
}
return 0;
}
內容 ：
有個建築師要設計一棟很高的大樓。這大樓會有許多樓層，每個樓層的面積必須大於它上一層的面積。再者，設計師 (他是某個西班牙足球隊的球迷) 要把每層樓漆成藍色或紅色，相鄰的兩個樓層顏色必須不同。
建築師現有 n 個特定顏色與面積的樓層可供建構大樓，每個樓層的面積均不同。建築師希望在上述的條件下以現有可用的樓層建構出最高的大樓。
輸入說明
：
輸入的第一行有測資的筆數 p。
每筆測資的第一行是可用的樓層數。接下來每一行代表一個樓層的顏色與面積。每個樓層以一個介於 -999999 與 999999
間的整數表示。沒有面積為 0 的樓層。負數為紅色樓層；正數則為藍色樓層。絕對值則是面積。沒有任何兩個樓層的面積相同。最大的樓層數為
500000。
輸出說明
：
每筆測資輸出依上述條件所得的最大樓層數於一行。
範例輸入 ：
2 5 7 -2 6 9 -3 8 11 -9 2 5 18 17 -15 4
範例輸出 ：
2 5
提示
：
出處
：
UVa ACM 11039
(管理：snail)
作法 : Greedy
分兩堆做好, 排序結束後, 從兩個陣列中交錯拿出符合且最大的數字
/**********************************************************************************/
/* Problem: d731 "11039 - Building designing" from UVa ACM 11039 */
/* Language: C */
/* Result: AC (196ms, 4236KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-27 20:01:41 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 2147483647
int A[500000], B[500000];
int cmp(const void *a, const void *b) {
int *aa, *bb;
aa = (int *)a, bb = (int *)b;
return *aa < *bb;
}
main() {
int t, n, x, a;
scanf("%d", &t);
while(scanf("%d", &n) == 1) {
int Aidx = 0, Bidx = 0;
for(a = 0; a < n; a++) {
scanf("%d", &x);
if(x > 0) A[Aidx++] = x;
else B[Bidx++] = -x;
}
qsort(A, Aidx, sizeof(int), cmp);
qsort(B, Bidx, sizeof(int), cmp);
int in1 = 0, in2 = 0, last = oo, flag = 0;
int tmp = 0, Ans = 0;
while(in1 <= Aidx && in2 <= Bidx) {
if(!flag) {
while(A[in1] > last && in1 < Aidx) in1++;
if(in1 == Aidx) break;
last = A[in1], in1++;
} else {
while(B[in2] > last && in2 < Bidx) in2++;
if(in2 == Bidx) break;
last = B[in2], in2++;
}
tmp++, flag = 1-flag;
}
Ans = Ans > tmp ? Ans : tmp;
in1 = 0, in2 = 0, last = oo, flag = 1, tmp = 0;
while(in1 <= Aidx && in2 <= Bidx) {
if(!flag) {
while(A[in1] > last && in1 < Aidx) in1++;
if(in1 == Aidx) break;
last = A[in1], in1++;
} else {
while(B[in2] > last && in2 < Bidx) in2++;
if(in2 == Bidx) break;
last = B[in2], in2++;
}
tmp++, flag = 1-flag;
}
Ans = Ans > tmp ? Ans : tmp;
printf("%d\n", Ans);
}
return 0;
}