1283问题 C: Middle Problem
时间限制: 1 Sec 内存限制: 128 MB
提交: 2802 解决: 405
[提交][状态][讨论版]
题目描述
Glory 是西电著名的 Sugar Daddy, 他会给他的粉丝发糖, 他现在有 n 个粉
丝, 每个粉丝手里有一定的糖果数量,现在 Glory 又想给他们再发一些糖, 一共
m 颗, 并希望发完糖之后所有粉丝拥有的糖果数量的中位数尽可能地大, 所以
他想问你再给某些人发一些糖之后, 中位数最多能提高到多少。
输入
多组数据,每一组数据第一行两个正整数 n,m, 0 < n ≤ 100000, 0 < m < 10^6
接下来一行包含 n 个数,每个数 0 ≤ a i ≤ 100000 表示标号为 i 的粉丝手里
目前的糖果数量
为了方便计算,所有的 n 都将会是奇数。
输出
对于每一组数据,输出一行包含一个数,表示粉丝拥有糖果数量的中位数在
Glory再次发糖后最高能是多少。
样例输入
3 1
1 1 1
3 2
1 1 1
样例输出
1
2
ac代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
int main(){int m,n;while(scanf("%d %d",&m,&n)!=EOF){int array[m];for(int i=0;i<m;i++){scanf("%d",&array[i]);}sort(array,array+m,less<int>());int kase,k,total=0;for(kase=(m-1)/2,k=kase+1;k<m;k++){total+=(array[k]-array[k-1])*(k-kase);if(n<=total)break;}if(n>total) {printf("%d\n",array[m-1]+(n-total)/(m-kase));continue;}else if(total==n) printf("%d\n",array[k]);else printf("%d\n",array[k-1]+((n-(total-((array[k]-array[k-1])*(k-kase))))/(k-kase)));}return 0;
}
解释：
粉丝的数量为奇数，这样中位数就是一个数。
下面研究发糖的规律：
（1）我们先将粉丝手中的糖设成一个数组，然后按升序排列数组，这样我们就知道最中间的那个糖，并且我们只用计算中间及其以后的部分。因为如果发糖到中间前面的部分，不如给直接发到中间及其后面部分更让中位数高，如1，2，3发5块糖，不给1发只给2，3发，肯定比都发的中位数高。
（2）分析情景，粉丝1，2，5，6，6发2块糖，按前面说的不管1和2，做法：给5要发一块，然后剩下的一块发给6（原来的5），6，6谁都一样，因为那个变成7的粉丝在最后排序的时候中位数还是6。
（3）分析情景，粉丝1，2，5，6，7发3块糖，有两种做法：一是给5，6，7一人发一块，二是给5发两块，给6发一块。显然，二做法更优，这就是代码中的n（糖数）与total（估计数）。估计数的意思是，5要发糖发到要与6齐平，需要一块，这个total=1小于n=3，那么5要与7齐平，需要2+1=3块，刚好。
代码实现：
（1）for(kase=(m-1)/2,k=kase+1;k<m;k++){
total+=(array[k]-array[k-1])*(k-kase);
if(n<=total)break;
}
kase是中位数，k是要与之齐平的数。不管钱前面的，要计算4，6，8齐平的估计数的算法：（8-4）+（8-6），但我们要是4，6，8，9，10，就要（10-4）等等吗，显示每次重复计算可能会超时超内存，我们换一种算法：（6-4）*（1-0）+（8-4）*（2-0）等等这样就减少了运算量，设计算法时要考虑到可变性。
（2）if(n>total) {
printf("%d\n",array[m-1]+(n-total)/(m-kase));
continue;
}
当n大于total时，中位数与最高数齐平，然后把剩下的n-total平分给中间及其后面的，利用int的取整性刚好解决5，5，5再发5块，中位数是5+1，（1为5/3）。
（3）等于不说了，
else printf("%d\n",array[k-1]+((n-(total-((array[k]-array[k-1])*(k-kase))))/(k-kase)));
这种情况是n<total,而再往后对齐又小于的情况，k-1是for循环后k++，再减去多余的
sort()函数
环境：#include<algorithm>
#include<functional>
using namespace std; 命名空间
在标准库中已经有现成的，是functional，functional提供了一堆基于模板的比较函数对象，它们是：equal_to<Type>、not_equal_to<Type>、greater<Type>、greater_equal<Type>、less<Type>、less_equal<Type>。
升序：sort(begin,end,less<data-type>()) //这个中英文翻译相反
降序：sort(begin,end,greater<data-type>())
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std; //简单使用方法
sort( A , A+100 , greater<int>() ); //降序排列
sort( A , A+100 , less<int>() ); //升序排列