Information
- ID
- 279
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 301
- Accepted
- 58
- Uploaded By
好像没有人发map映射呀,那我来插一脚。其实主要用到桶排的思想,只不过map更加节约时间
#include<stdio.h>
#include<map>
#include<iostream>
using namespace std;
const int N = 1e6;
int n,c,ans = 0;
int num[N];
map<int,int>a;
int main()
{
scanf("%d %d",&n,&c);
for(int i = 0;i<n;i ++)
{
scanf("%d",&num[i]);
a[num[i]]++;
}
for(int i = 0;i<n;i++)
{
ans +=a[num[i]+c];
}
printf("%d",ans);
return 0;
}
#include <iostream>
#include <algorithm>
using namespace std;
// 1 1 2 3 C = 1
int erfen2(int* arr,long long key,int N) {
int l = -1;
int r = N;
while (l + 1 < r) {
int mid = l + ((r - l) >> 1);
if (l == -1) {
mid = (l + r) >> 1;
}
if (arr[mid] <= key) {
l = mid;
}
else {
r = mid;
}
}
return r;//大于 key 的 第一个值,r - 1 是 key 的右边界
}
int erfen2B(int* arr, long long key, int N) {
int l = -1, r = N;
while (l + 1 < r) {
int mid = l + ((r - l) >> 1);
if (l == -1) {
mid = (l + r) >> 1;
}
if (arr[mid] >= key) {
r = mid;
}
else {
l = mid;
}
}
return l;//小于 key 的 第一个值, l + 1 是 key 的 左边界。
}
int main(void) {
int N, C;
cin >> N >> C;
int* arr = new int[N + 5];
for (int i = 0; i < N; ++i) {
cin >> arr[i];
}
sort(arr, arr + N);
int ans = 0;
for (int i = 0; i < N; ++i) {
long long temp = arr[i] + C;// 我们只要找到这个值就行了。
ans += erfen2(arr, temp, N) -1 - erfen2B(arr, temp, N);
}
cout << ans << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int a[N];
int b[N];
int n;//以下是两个自己常用版子,
int find(int x){ //求右边界,若求大于某个数的第一个位置就在return r+1
int l=0,r=n-1;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>x){
r=mid-1;
}
else{
l=mid+1;
}
}
return r;
}
int find1(int x){//求小于某个数的第一个位置,同上理若求左边界就只需ruturn l
int l=0,r=n-1;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>=x){
r=mid-1;
}
else{
l=mid+1;
}
}
return l-1;
}
int main(){
int x;
cin>>n>>x;
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
int num;
int ans=0;
for(int i=0;i<n;i++){
num=a[i]+x;
ans+=find(num)-find1(num);
}
cout<<ans;
return 0;
}
方法一
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,c,l,r,ans;
ll a[1000005];//数据有点大
int main()
{
cin>>n>>c;
for(int i=0;i<n;++i)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=0;i<n;++i)
{
l=lower_bound(a,a+n,a[i]+c)-a;//不懂的建议百度
r=upper_bound(a,a+n,a[i]+c)-a;
ans+=r-l;
}
cout<<ans;
return 0;
}
方法二 (和做法一思路一样)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,x,h;
int a[1000000];
int find1(int x)//找小于等于a[i]-C的数的函数
{
int l=0,r=n+1,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(a[mid]<=x)l=mid;
else r=mid;
}
return l;
}
int find2(int x)
{
int l=0,r=n+1,mid;
while(l+1<r)
{
mid=(l+r)/2;
if(a[mid]<x) l=mid;
else r=mid;
}
return l;
}
int main()
{
cin>>n>>x;
for(int i=1; i<=n; i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1; i<=n; i++)
{
h+=find1(a[i]+x)-find2(a[i]+x);
}
cout<<h;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.