当前位置:网站首页>(POJ - 3579) median (two points)
(POJ - 3579) median (two points)
2022-07-06 16:09:00 【AC__ dream】
Chinese question meaning : Now there is N A mysterious number (A1,A2,A3….An), We need to get a password from this string of numbers .
The way to get the password is :
First calculate the difference between each number :|Ai-Aj|(1<=i<j<=N), In the end, you can get C Difference .
The final password is the median of these numbers .
If C It's even , It is stipulated that the median is C/2 Small difference .
This question and POJ-3579 The method of question is similar , We also solve it by dichotomy , For each number to be bisected x, We go through check Function to determine whether it is less than or equal to x How many pairs of distances are there , If the distance is less than or equal to x The number of pairs of is greater than half of the logarithm of the total , that r=x, conversely l=x+1, How should the specific dichotomy be carried out ? Let's start with a Sort the array from small to large , The dichotomy is found in ai On the right and the distance is less than or equal to x The number of , because aj-ai It is monotonically increasing , So this process is carried out through dichotomy , Traverse in turn ai, The distance is less than x Number to number , Two points are enough , There are quite a lot of details , See the code for details :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000003;
int a[N],n;
bool check(int x)// Find that the distance is less than or equal to x How many pairs are there , More than half the logarithm of all numbers returns true, Otherwise return to false
{
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=upper_bound(a+1,a+n+1,a[i]+x)-a-i-1;
if(cnt>=((long long)n*(n-1)/2+1)/2) return true;
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=1000000000,mid;
while(l<r)
{
mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
}
return 0;
}
边栏推荐
- Opencv learning log 32 edge extraction
- 信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志
- Penetration test (7) -- vulnerability scanning tool Nessus
- 渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
- Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
- Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
- 【练习-2】(Uva 712) S-Trees (S树)
- Socket communication
- [exercise -11] 4 values why sum is 0 (and 4 values of 0)
- [analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
猜你喜欢
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
PySide6 信号、槽
860. Lemonade change
2078. Two houses with different colors and the farthest distance
921. Minimum additions to make parentheses valid
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
Gartner:关于零信任网络访问最佳实践的五个建议
Determine the Photo Position
【高老师软件需求分析】20级云班课习题答案合集
2027. Minimum number of operations to convert strings
随机推荐
C basic grammar
X-Forwarded-For详解、如何获取到客户端IP
SSM框架常用配置文件
Opencv learning log 19 skin grinding
Configuration du cadre flask loguru log Library
(POJ - 2739) sum of constructive prime numbers (ruler or two points)
HDU - 6024 building shops (girls' competition)
Radar equipment (greedy)
E. Breaking the Wall
渗透测试 ( 1 ) --- 必备 工具、导航
Find 3-friendly Integers
Opencv learning log 14 - count the number of coins in the picture (regardless of overlap)
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
滲透測試 ( 1 ) --- 必備 工具、導航
605. Planting flowers
2027. Minimum number of operations to convert strings
Write web games in C language
Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
对iptables进行常规操作
China's peripheral catheter market trend report, technological innovation and market forecast