。。。。我发现scanf比cin快了80倍。。。。我受到了惊吓

练练快排就是了。

带权中位数。

证法就跟证C(1,n) C(2,n) C(3,n) ... C(n,n) 中哪个最大，原理如出一辙。

数学老师应该讲过了吧~

我对这题彻底无语..

以前做的错的

现在才发现错误的地方非常恶心。

我的两个变量记录下标，结果就把这两个变量输出了，还有10分。。

然后又因为Qsort了两次，第一次记录的下标不是对应原来的那个了，最后每算出一个就输出一个，才过。。速度也不快,247ms+

还有必须用long long，用long的结果就是wa 7个点。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 40ms

├ 测试数据 09：答案正确... 165ms

├ 测试数据 10：答案正确... 165ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：379ms

分别将X坐标和Y坐标两次快排，再枚举每个X坐标和Y坐标。

很多 C++ 编译器的 cin 都是很慢的，和 constructor 和 destructor 有关

一种方法是按横坐标排序，从左到右累加权值，当权值累加值大于等于总权值一半时停止

for (i = 0, s = 0; s < w/2; ++i)

s += a[i].w;

printf("%d ", a.x);

纵坐标类似

另一种是带权中位数的线性算法

提醒大家不要在vijos上用cin输入

这是同一个程序(输入部分不同)在同一测评机上的结果

用scanf输入:

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 41ms

用cin输入

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 400ms

├ 测试数据 07：答案正确... 978ms

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

long int 其实也可以的

struct point

{

long int x;

long int y;

long int f;

}p[100001];

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：137ms

挺简单的题，为什么这么少人AC？

多长时间了，终于一次AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：144ms

正交分解，很好很强大。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 9ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：365ms

都来鄙视我吧，数组开过了啊啊啊啊~~~~

排序后，记录序号，要用__int64！！！

加权中位数。。。

数据太弱。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：112ms

带权中位数...矢量运算正交分解...楼上的都这么专业...

问题可以转化为找一个X是所有X的权值最小，找一个Y是所有Y的权值最小，

先求出所有X，Y的权值和，，然后减去就可以找到中位数

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

排两个序，带权的中位数就好了

汗水！！

楼下的“Sqort”

qsort+中位数枚举过了，100ms以内

分别按横纵坐标排序

把一个点的需求和人口相乘为a，把它看成这个坐标的点有a个

求横坐标和纵坐标的中位数

研究物理的...矢量运算正交分解+2分查找。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：137ms

为什么不能全0ms。。。。