当前位置:网站首页>洛谷P1102 A-B数对(二分,map,双指针)
洛谷P1102 A-B数对(二分,map,双指针)
2022-07-06 09:25:00 【是小张张呀 zsy】
简单A-B
描述
这是一道简单题,给出一串数以及一个数字C,要求计算出所有A - B = C的数对的个数(不同位置的数字一样的数对算不同的数对)。
输入
输入共两行。
第一行,两个整数N, C。1=<N<=2e5 , C>=1
第二行,N个整数,作为要求处理的那串数。
输出
一行,表示该串数中包含的满足A - B =C的数对的个数。
输入样例 1
4 1
1 1 2 3
输出样例 1
3
输入样例 2
6 1
1 1 1 2 2 2
输出样例 2
9
本题值得注意的是,有可能暴int
比如
输入
200000 1
1e5个1,1e5个2
输出
1e10 > int型
(int存最大的数约等于2e9)
二分
简单二分模板题
先排序,找出比第i个数大C的最左端点的坐标和最右端点的坐标,(右端点坐标减去左端点坐标加1)就表示有多少个比第i个数大C
例如样例2中
#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);
//节约cin,cout时间;
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) //找最左端点;r=mid;
{
int mid=l+r >>1;
//相当于(l+r)/2,这么写看着厉害一点hh,+优先级大于>>(右移)优先级;
if(a[mid]-a[i]>=c)
r=mid;
else
l=mid+1;
}
int k=l;
l=i+1,r=n;
while(l<r)//找最右端点;l=mid;
{
int mid=l+r+1 >> 1;//改l,要+1,防止死循环
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);
//节约cin,cout时间;
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i]+c;//用b[N]数组存(对应的)的大C的值
}
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;//返回第一个大于等于b[i]的a数组的下标
int kk=upper_bound(a+1,a+n+1,b[i])-a;//返回大于
res+=kk-k;//因为upper_bound返回大于的下标,所以无需加1
}
cout<<res<<endl;
return 0;
}
双指针
具体的实现就是,我们维护两个端点kk , k,每次kk右移到a[kk] - a[i] <= c
的最后位置的下一位,k右移到满足a[k] - a[l] < c
最后一位.
也就是说, 此时如果a[kk] - a[i] == c && a[k] - a[i] == c
,中间的那一段一定都是满足条件的,我们让res += kk - k
即可。
#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);
//节约cin,cout时间;
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++; //因为是有序的,下次寻找从kk开始;减少不必要的枚举
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 时间复杂度O(n)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map> //map头文件;
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;建立一个数字到出现次数的映射 map<a[i],times>
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//节约cin,cout时间;
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;
}
边栏推荐
- LeetCode#268. Missing numbers
- cs零基础入门学习记录
- China's salt water membrane market trend report, technological innovation and market forecast
- 数据在内存中的存储&载入内存,让程序运行起来
- Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
- MySQL transactions
- STM32 learning record: input capture application
- LeetCode#53. Maximum subarray sum
- UCORE LaB6 scheduler experiment report
- The most detailed postman interface test tutorial in the whole network. An article meets your needs
猜你喜欢
ucore lab7
Winter vacation daily question - maximum number of balloons
Learning records: serial communication and solutions to errors encountered
学习记录:使用STM32F1看门狗
LeetCode#237. Delete nodes in the linked list
Learning record: use stm32f1 watchdog
基于485总线的评分系统
ucorelab3
The most detailed postman interface test tutorial in the whole network. An article meets your needs
Servlet
随机推荐
学习记录:理解 SysTick系统定时器,编写延时函数
Research Report on market supply and demand and strategy of China's land incineration plant industry
ucore lab 6
Es6--- two methods of capturing promise status as failed
学习记录:串口通信和遇到的错误解决方法
Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
Research Report on market supply and demand and strategy of China's medical chair industry
Crawler series (9): item+pipeline data storage
学习记录:USART—串口通讯
Crawling cat's eye movie review, data visualization analysis source code operation instructions
What to do when programmers don't modify bugs? I teach you
JS --- detailed explanation of JS DOM (IV)
Cost accounting [13]
Scoring system based on 485 bus
Leetcode notes - dynamic planning -day6
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
ucore lab 6
Jupyter installation and use tutorial
Eslint--- error: newline required at end of file but not found (EOL last) solution
What are the commonly used SQL statements in software testing?