题解3 带权中位数（线性版）

链接：https://ac.nowcoder.com/acm/contest/20960/1013 来源：牛客网

思路：其实是一个结论，这篇博客记录下自己犯的低级错误。结论：第一次出现的前缀和人数>=总人数半数的点为所求点。

低级错误：1.把记录每个点的人数的数组设成了int型。其实这本没错，但因为自己后来突然想着把这个数组重复利用为前缀和数组，节省空间，这下就出事了，因为总人数最多可以达到4e11级别，必须要long long类型才能记录下前缀和（如果你通过率50%，不妨看看是不是设成int型了） 2.对于处在边界处的结论没考虑清楚。解决方法：后来为了一步到位，干脆把用double类型定义一个half=sum/2来记录人数的一半，这下比较某个位置的前缀和是否>=half就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
long long people[200010];
int main()
{
    int n,l,t=0;
    long long sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){scanf("%d",&l);}//使用了结论，这个位置变量就没用了
    people[0]=0;
    for(int i=1;i<=n;i++){scanf("%d",&t);people[i]=t+people[i-1];sum+=t;}
    double half=sum/2;
    for(int i=1;i<=n;i++){if(people[i]>=half){printf("%d",i);break;}}
    return 0;
}