麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

POJ 3579 Median(2次二分)

2019-11-10 20:13:20
字體:
供稿:網(wǎng)友

Given N numbers, X1,X2, ... , XN, let us calculate the difference of every pair of numbers: ∣Xi- Xj∣ (1 ≤ i j N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this PRoblem, the median is defined as the (m/2)-th  smallest number ifm,the amount of the differences, is even. For example, you have to find the third smallest one in the case ofm = 6.

Input

The input consists of several test cases.In each test case, N will be given in the first line. Then N numbers are given, representingX1, X2, ... ,XN, ( Xi≤ 1,000,000,000  3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input
41 3 2 431 10 2Sample Output
18

  思路:本題直接使用暴力法,時間復(fù)雜度約為n^2,超時,所以采用二分法。

  先把差值分出來,再用二分法驗證差值是否符合要求。

#include<algorithm>#include<cstdio>#include<cstdlib>using namespace std;int n,m;int str[100005];int judge(int mid){   int cnt=0;    for(int i=0;i<n;i++)    {        cnt+=n-(lower_bound(str,str+n,str[i]+mid)-str);//C++中STL的查找函數(shù)
    }    return cnt>m?1:0;}int main(){   //freopen("e://in.txt","r",stdin);    while(scanf("%d",&n)==1)    {     m=n*(n-1)/4;         for(int i=0;i<n;i++)          scanf("%d",&str[i]);          sort(str,str+n);          int left=0,right=str[n-1]+str[0],mid;          while(left<=right)          {              mid=(left+right)/2;              if(judge(mid))                left=mid+1;              else                right=mid-1;          }          printf("%d/n",left-1);    }    return 0;}

總結(jié):lower_bound函數(shù)的引用

 


發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 亚洲乱码精品久久久久 | 精品国产一区二区三区在线观看 | 精品国产一区二区三区天美传媒 | 免费a网 | 国产在线精品一区二区 | 毛片a区 | 中文字幕在线观看精品 | 在线观看国产www | 免费中文视频 | 久久亚洲网 | 欧美一级黄视频 | 国产午夜电影在线观看 | 亚洲第一页夜 | av在线1| 毛片免费观看视频 | 美女亚洲| 国产精品自在线拍 | 亚洲欧美日韩免费 | 亚洲 综合 欧美 动漫 丝袜图 | 在线亚洲欧美 | 免费看成人av | 精品国产一区二区久久 | 神马久久精品综合 | 国产黄色免费网站 | 色播视频在线播放 | av视在线 | 国产午夜精品一区二区三区在线观看 | 中文字幕www| 久久久久久艹 | 久久精品久久久久 | 手机免费看一级片 | 久久久久电影网站 | 国产精品美女久久久免费 | 综合精品久久 | 综合精品视频 | 特片网久久 | 成人毛片免费看 | 国产精品一品二区三区四区18 | 亚洲成人涩涩 | 12av电影 | 久久久aa |