2011-10-27 12:38:59Morris
a277. 高手寂寞
a277. 高手寂寞
/**********************************************************************************/
/* Problem: a277 "高手寂寞" from */
/* Language: C (1004 Bytes) */
/* Result: AC(604ms, 1.6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-27 08:55:55 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 1000000000
int A[100001], flag;
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
int Find_Median(long long n) {
long long Gap = n*(n-1)/2, tmp1, tmp2;
int l = 0, m, r = oo, i, flag = 0;
int idx;
Gap = Gap/2 + (Gap%2 != 0);
do {
m = (l + r)/2, tmp1 = 0, tmp2 = 0, flag = 0;
idx = 0;
for(i = 0; i < n; i++) {
while(idx < n && A[idx]-A[i] <= m) {
if(A[idx]-A[i] == m) flag = 1;
idx++;
}
tmp1 += idx - i - 1;
}
if(flag) {
idx = 0;
for(i = 0; i < n; i++) {
while(idx < n && A[idx]-A[i] < m)
idx++;
tmp2 += idx - i - 1;
}
}
if(tmp1 >= Gap && tmp2 < Gap && flag != 0) return m;
if(tmp1 < Gap) l = m+1;
else r = m-1;
} while(l <= r);
}
int main() {
int i, j, n, k = 0;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
qsort(A, n, sizeof(int), cmp);
printf("%d\n", Find_Median(n));
}
return 0;
}
內容 ：
差距，永遠是差距；不懂，永遠是不懂─［高手寂寞］依韻
人的實力難免會有些許的落差，而今天你擁有了一支軍隊，
你想要以中位數大略估計一下軍隊中實力落差的嚴重程度，
假設有k組差距，則中位數定義為排序後從小數來第k/2組
輸入說明
：
多組輸入，以EOF作為結束
第一行有一個正整數n(2<=n<=100000)，代表軍隊中有n個人
第二行有n個正整數Ai(0<Ai<=1000000000)，代表每個人實力量化後的數值
輸出說明
：
一個數字，代表軍中C(n,2)=n*(n-1)/2組差距中的中位數
範例輸入 ：
3 1 3 9 4 1 2 3 4
範例輸出 ：
6 1
提示
：
第一組範例：
(1,3) => 2
(3,9) => 6
(1,9) => 8
而2,6,8的中位數為6
若k為偶數時直接取第k/2個數字即可，不必平均
第二組範例：
1,1,1,2,2,3 之 中位數為 1
出處
：
/**********************************************************************************/
/* Problem: a277 "高手寂寞" from */
/* Language: C (1004 Bytes) */
/* Result: AC(604ms, 1.6MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-27 08:55:55 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define oo 1000000000
int A[100001], flag;
int cmp(const void *i, const void *j) {
return *(int *)i - *(int *)j;
}
int Find_Median(long long n) {
long long Gap = n*(n-1)/2, tmp1, tmp2;
int l = 0, m, r = oo, i, flag = 0;
int idx;
Gap = Gap/2 + (Gap%2 != 0);
do {
m = (l + r)/2, tmp1 = 0, tmp2 = 0, flag = 0;
idx = 0;
for(i = 0; i < n; i++) {
while(idx < n && A[idx]-A[i] <= m) {
if(A[idx]-A[i] == m) flag = 1;
idx++;
}
tmp1 += idx - i - 1;
}
if(flag) {
idx = 0;
for(i = 0; i < n; i++) {
while(idx < n && A[idx]-A[i] < m)
idx++;
tmp2 += idx - i - 1;
}
}
if(tmp1 >= Gap && tmp2 < Gap && flag != 0) return m;
if(tmp1 < Gap) l = m+1;
else r = m-1;
} while(l <= r);
}
int main() {
int i, j, n, k = 0;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
qsort(A, n, sizeof(int), cmp);
printf("%d\n", Find_Median(n));
}
return 0;
}
上一篇：a245. 王老師愛兩條線
下一篇：a271. 彩色蘿蔔