2011-06-13 22:26:36Morris
d961. A. 耶誕老人到你家
http://zerojudge.tw/ShowProblem?problemid=d961
內容 ：
一年一度的耶誕節即將到來，但是耶誕老人的麋鹿卻意外得了重感冒無法出門，導致他陷入禮物送不出的窘境，而這將會造成世界上所有乖寶寶變壞的可怕後果！
情急之下，耶誕老人想借用你飼養的奶牛們擔任運送禮物的任務，他願意拿出所有你能裝進箱子的禮物作為交換，但是每個箱子都只能裝一個禮物，也不能把禮物或箱子割開。興奮的你迅速翻出家裡所有的空箱子，打算狠狠地撈這位可憐的耶誕老人一票！
輸入說明
：
測資包含多組測試資料，第一列有一個整數 T 表示接下來有幾組測試資料。
每組測試資料共有三列，第一列有兩個整數 N, M，分別代表禮物與箱子數量，第二列有 N 個整數表示各個禮物的大小，第三列有 M 個整數表示各個箱子的大小，禮物與箱子的大小皆介於 1 至 231 - 1 之間 (1 ≤ N, M ≤ 50000)。若 x ≤ y，則一個大小為 x 的禮物可以裝在一個大小為 y 的箱子裡面。
輸出說明
：
對每筆測試資料輸出你能帶走的禮物數量，若你無法帶走任何禮物則輸出 “Santa Claus wishes you get AC in the next submission.”。
範例輸入 ：
2 4 5 5 10 15 20 10 10 10 10 10 1 1 10 5
範例輸出 ：
2 Santa Claus wishes you get AC in the next submission.
提示
：
出處
：
先將禮物跟盒子分別由小排到大
盒子裝不下禮物，則換下一個大盒子 ... 持續
/**********************************************************************************/
/* Problem: d961 "A. 耶誕老人到你家" from 2010 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (128ms, 844KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-11 09:25:44 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
int t;
}Data;
Data X[50000];
void Merge(int l, int m, int h, Data A[]) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= h)
if((A[In1].t < A[In2].t))
X[Top++] = A[In1++];
else X[Top++] = A[In2++];
while(In1 <= m) X[Top++] = A[In1++];
while(In2 <= h) X[Top++] = A[In2++];
for(a=0,b=l;a<Top;a++,b++)
A[b]=X[a];
}
void MergeSort(int l, int h, Data A[]) {
if(l < h) {
int m = (l+h)/2;
MergeSort(l , m, A);
MergeSort(m+1, h, A);
Merge(l, m, h, A);
}
}
main() {
int t, n, m, a;
Data A[50000], B[50000];
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(a = 0; a < n; a++) scanf("%d", &A[a].t);
for(a = 0; a < m; a++) scanf("%d", &B[a].t);
MergeSort(0, n-1, A);
MergeSort(0, m-1, B);
int in1 = 0, in2 = 0, Ans = 0;
for(; in1 < n && in2 < m; in2++) {
if(A[in1].t <= B[in2].t)
Ans++, in1++;
}
if(Ans) printf("%d\n", Ans);
else puts("Santa Claus wishes you get AC in the next submission.");
}
return 0;
}
上一篇：d951. B. 好吃的麵包
下一篇：b238. A. 腹黑、傲嬌