当前位置:网站首页>Luogu P1102 A-B number pair (dichotomy, map, double pointer)
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】
Simple A-B
describe
This is a simple question , Give a string of numbers and a number C, Ask to calculate all A - B = C The number of pairs of ( The same number pairs in different positions count different number pairs ).
Input
There are two lines of input .
first line , Two integers N, C.1=<N<=2e5 , C>=1
The second line ,N It's an integer , As the number of strings required to be processed .
Output
a line , Indicates that the number contained in the string satisfies A - B =C The number of pairs of .
sample input 1
4 1
1 1 2 3
sample output 1
3
sample input 2
6 1
1 1 1 2 2 2
sample output 2
9
It is worth noting that , May be violent int
such as
Input
200000 1
1e5 individual 1,1e5 individual 2
Output
1e10 > int type
(int The maximum number of deposits is about 2e9)
Two points
Simple dichotomous template question
Prioritize , Find out bidi i It's a big number C Coordinates of the leftmost endpoint and the rightmost endpoint of ,( Right endpoint coordinates minus left endpoint coordinates plus 1) It means how many are better than i It's a big number C
Examples 2 in
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N];
ll res;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// save cin,cout Time ;
cin>>n>>c;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int l=i+1,r=n;
while(l<r) // Find the leftmost endpoint ;r=mid;
{
int mid=l+r >>1;
// amount to (l+r)/2, It looks a little more powerful hh,+ Priority is greater than >>( Move right ) priority ;
if(a[mid]-a[i]>=c)
r=mid;
else
l=mid+1;
}
int k=l;
l=i+1,r=n;
while(l<r)// Find the rightmost endpoint ;l=mid;
{
int mid=l+r+1 >> 1;// Change l, want +1, Prevent a dead cycle
if(a[mid]-a[i]<=c)
l=mid;
else
r=mid-1;
}
int kk=l;
if(a[kk]-a[i]==c&&a[k]-a[i]==c)
res+=kk-k+1;
}
cout<<res<<endl;
return 0;
}
lower_bound()
upper_bound()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N],b[N];
ll res;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// save cin,cout Time ;
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]+c;// use b[N] Array storage ( Corresponding ) The big C Value
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int k=lower_bound(a+1,a+n+1,b[i])-a;// Returns the first greater than or equal to b[i] Of a Index of the array
int kk=upper_bound(a+1,a+n+1,b[i])-a;// Return is greater than the
res+=kk-k;// because upper_bound Returns a subscript greater than , So there's no need to add 1
}
cout<<res<<endl;
return 0;
}
Double pointer
The concrete realization is , We maintain two endpoints kk , k, Every time kk Move right to a[kk] - a[i] <= c
Next to the last position of ,k Move right to meet a[k] - a[l] < c
Last .
in other words , If at this time a[kk] - a[i] == c && a[k] - a[i] == c
, The middle paragraph must meet the conditions , We let res += kk - k
that will do .
#include <bits/stdc++.h>
using namespace std;
int const N=200010;
typedef long long ll;
int a[N],n,c;
ll res;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// save cin,cout Time ;
cin>>n>>c;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int kk=2,k=2;
for(int i=1;i<=n;i++)
{
while(kk<=n&&a[kk]-a[i]<=c)
kk++; // Because it's orderly , Next time look for kk Start ; Reduce unnecessary enumeration
while(k<=n&&a[k]-a[i]<c)
k++;
if(a[kk-1]-a[i]==c&&a[k]-a[i]==c)
res+=kk-k;
}
cout<<res<<endl;
return 0;
}
MAP Time complexity O(n)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map> //map The header file ;
using namespace std;
typedef long long ll;
int const N=2e5+10;
int n,c,a[N],b[N];
ll res;
map<int,int> mp;//key-value; Establish a number to occurrence mapping map<a[i],times>
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// save cin,cout Time ;
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
res+=mp[a[i]+c];
}
cout<<res<<endl;
return 0;
}
边栏推荐
- [exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
- SSM框架常用配置文件
- Cost accounting [21]
- Opencv learning log 32 edge extraction
- F - Birthday Cake(山东省赛)
- [exercise-7] crossover answers
- Ball Dropping
- 区间和------离散化
- Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
猜你喜欢
Borg Maze (BFS+最小生成树)(解题报告)
Ball Dropping
[exercise-5] (UVA 839) not so mobile (balance)
Penetration test (7) -- vulnerability scanning tool Nessus
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
C语言数组的概念
X-forwarded-for details, how to get the client IP
X-Forwarded-For详解、如何获取到客户端IP
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
Optimization method of path problem before dynamic planning
随机推荐
1010 things that college students majoring in it must do before graduation
Perform general operations on iptables
Find 3-friendly Integers
Opencv learning log 19 skin grinding
The most complete programming language online API document
Cost accounting [24]
F - Birthday Cake(山东省赛)
C语言必背代码大全
【练习-9】Zombie’s Treasure Chest
Common configuration files of SSM framework
Accounting regulations and professional ethics [1]
VS2019初步使用
Determine the Photo Position
Cost accounting [20]
差分(一维,二维,三维) 蓝桥杯三体攻击
China chart recorder market trend report, technology dynamic innovation and market forecast
Opencv learning log 30 -- histogram equalization
快速转 TypeScript 指南
Matlab comprehensive exercise: application in signal and system
区间和------离散化