A题：
Weighted Median
Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
For n elements x1, x2, ..., xn with positive integer weights w1, w2, ..., wn. The weighted median is the element xk satisfying
and 
,
S indicates
and ,S indicates
Can you compute the weighted median in O(n) worst-case?
输入
There are several test cases. For each case, the first line contains one integer n(1 ≤ n ≤ 10^7) — the number of elements in the sequence. The following line contains n integer numbers xi (0 ≤ xi ≤ 10^9). The last line
contains n integer numbers wi (0 < wi < 10^9).
contains n integer numbers wi (0 < wi < 10^9).
输出
One line for each case, print a single integer number— the weighted median of the sequence.
示例输入
7 10 35 5 10 15 5 20 10 35 5 10 15 5 20
示例输出
20
提示
The S which indicates the sum of all weights may be exceed a 32-bit integer. If S is 5, 
equals 2.5.
equals 2.5.来源
2014年山东省第五届ACM大学生程序设计竞赛
示例程序
解题思路：
题目说让用O（n）的算法来走，但是最后我还用了nlogn的方法，用了sort预先处理了一下。然后算出排完顺序后的前缀和，用sum-前缀和-这个位置的权重得到了后缀和，
然后再依次枚举出了最后的结果。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 10000000
struct node
{
int value;
int wei;
}a[MAX];
int cmp ( const struct node & x, const struct node & y )
{
return x.value < y.value;
}
int main(void)
{
int n;
while ( cin>>n )
{
for ( int i = 0;i < n;i++ )
{
cin>>a[i].value;
}
long long sum = 0;
for ( int i = 0;i < n;i++ )
{
cin>>a[i].wei;
sum+=a[i].wei;
}
long double sum1 = 1.0*sum/2;
sort(a,a+n,cmp);
long long max_limit = 0;
long long min_limit = 0;
int pos_wei;
for ( int i = 1;i < n-1;i++ )
{
min_limit = min_limit + a[i-1].wei;
max_limit = sum - min_limit - a[i].wei;
if ( min_limit < sum1 && (max_limit <= sum1) )
{
pos_wei = a[i].value;
break;
}
}
cout<<pos_wei<<endl;
}
return 0;
}
B题：
YC大牛的判题任务
Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld
Java class name: Main
第七届北京师范大学程序设计竞赛要开始了.今年的比赛规模比以前大多了,而且还要邀请外校的大牛来友情参赛.
今年比赛系统采用了我们YC大牛编写的OJ(OnlineJudge).为了更好的服务校赛,YC大牛准备测试一下OJ的判题效率.
他测试的方法是,先提交N个程序,然后打开判题程序开始判题,每次都只判一个题目,当有一个题目在OJ上运行的时候,其他程序就只有等待.当一个程序运行完后,会立刻选择另外一个程序来运行,直到所有程序都在OJ上判完.
YC会测定一下所有程序的等待时间之和,以此作为判题效率的指标.
现在YC大牛做了一次测试,他想看看实际判题结果和理论上最优的判题结果有多大差异.现在给你所有题目在实际判题的时候的运行时间,让你找出理论上使等待时间总和最小的判题顺序(存在多个相同等待时间的判题方案时候,让编号小的尽可能先判.)
今年比赛系统采用了我们YC大牛编写的OJ(OnlineJudge).为了更好的服务校赛,YC大牛准备测试一下OJ的判题效率.
他测试的方法是,先提交N个程序,然后打开判题程序开始判题,每次都只判一个题目,当有一个题目在OJ上运行的时候,其他程序就只有等待.当一个程序运行完后,会立刻选择另外一个程序来运行,直到所有程序都在OJ上判完.
YC会测定一下所有程序的等待时间之和,以此作为判题效率的指标.
现在YC大牛做了一次测试,他想看看实际判题结果和理论上最优的判题结果有多大差异.现在给你所有题目在实际判题的时候的运行时间,让你找出理论上使等待时间总和最小的判题顺序(存在多个相同等待时间的判题方案时候,让编号小的尽可能先判.)
Input
第1行是一个整数N,代表测试数据的组数.
第2行开始的N行,每行是一组测试数据.
从第2行到N+1行每行以一个M(0<=M<=3000)开始,代表有M个程序等待判题,接着是M个整数,依次代表从编号1到M的题目的运行时间.
第2行开始的N行,每行是一组测试数据.
从第2行到N+1行每行以一个M(0<=M<=3000)开始,代表有M个程序等待判题,接着是M个整数,依次代表从编号1到M的题目的运行时间.
Output
对应于每组输入,首先输出数据编号(如样例所示),然后输出M个数,代表最优的判题顺序.
Sample Input
2 5 1 1 1 1 1 6 1 2 3 4 5 6
Sample Output
Case 1: 1 2 3 4 5 Case 2: 1 2 3 4 5 6
Source
解题思路：
这道题其实也是简单的贪心问题，但是这道题让我学会了stable_sort()函数和sort()函数的区别，我知道了，如果使用sort函数的话，会对于两个相等的元素进行换位处理，但是如果是stable_sort()就是我们说的稳固排序的话，我们就不会怕这样的情况产生了，比如说1 4 6 4' 9 。。用sort拍完后，会产生 1 4' 4 9 的情况，而如果用stable_sort()排完后，肯定是1 4 4' 9，题目要求的是，如果等待时间相同，那么就输出题目编号较小的那个题号。。。这样看来，我用sort交了4次，都是WA，，用stable_sort一次就A了。。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
using namespace std;
# define MAX 3333+4
struct node
{
int time;
int id;
}a[MAX];
int cmp ( const struct node & x,const struct node & y )
{
return x.time < y.time;
}
int main(void)
{
int t;cin>>t;
int icase = 1;
while ( t-- )
{
int n;cin>>n;
for ( int i = 0;i < n;i++ )
{
cin>>a[i].time;
a[i].id = i+1;
}
stable_sort(a,a+n,cmp);
printf("Case %d:",icase++);
for ( int i = 0;i < n;i++ )
{
cout<<" "<<a[i].id;
}
cout<<endl;
}
return 0;
}