Help cupid
Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13308&courseid=0
Mean:
地球被划分为24个时区(-11~23),现在给出n个人的时区,将这n个人两两配对,使得n/2对配偶的时区差值之和最小。
analyse:
由于给的都是整数,而且只有24个时区,首先统计每个时区有多少人。
然后每个时区的人数都%2,因为同一时区的两个人差值为0。
接着就是枚举人数不为零的时区的人数。
根据贪心的思想,我们知道除了第一个和最后一个外,其他人都是和相邻两个的其中一个匹配,为什么呢?自己画个圈去证明。
对于第一个和最后一个,要么最后特判一下,要么直接在数组后面接一个每个元素+24的数组(处理环常用方法),暴力一下就行。
Time complexity: O(N)
Source code:
);
;;;;
;
;;;;
;;
;) ;
}
/*
;;;;
;
;;;;
;;
;) ;
}
/*
*/