P1102 A-B數(shù)對

題目描述

出題是一件痛苦的事情！

題目看多了也有審美疲勞，于是我舍棄了大家所熟悉的A+B Problem，改用A-B了哈哈！

好吧，題目是這樣的：給出一串?dāng)?shù)以及一個數(shù)字C，要求計算出所有A-B=C的數(shù)對的個數(shù)。（不同位置的數(shù)字一樣的數(shù)對算不同的數(shù)對）

輸入輸出格式

輸入格式：

?

第一行包括2個非負(fù)整數(shù)N和C，中間用空格隔開。

第二行有N個整數(shù)，中間用空格隔開，作為要求處理的那串?dāng)?shù)。

?

輸出格式：

?

輸出一行，表示該串?dāng)?shù)中包含的所有滿足A-B=C的數(shù)對的個數(shù)。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 4 1 1 1 2 3 輸出樣例#1：?復(fù)制 3

說明

對于73%的數(shù)據(jù)，N <= 2000；

對于100%的數(shù)據(jù)，N <= 200000。

所有輸入數(shù)據(jù)都在longint范圍內(nèi)。

2017/4/29新添數(shù)據(jù)兩組

?

sort排序+模擬84分

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 200100 #define ll long long using namespace std; ll n,c,b,ans,a[N]; ll read() {ll x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int main() {n=read(),c=read(),b=1;for(int i=1;i<=n;i++)a[i]=read();sort(a+1,a+1+n);for(int i=1;i<=n;i++)for(int j=b;j<i;j++)if(a[i]-a[j]<=c)if(a[i]-a[j]==c) ans++;else break;else b=j;printf("%lld",ans);return 0; } 84分代碼

map AC

#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 200100 #define ll long long using namespace std; map<int,int>m; ll n,c,ans,a[N],maxn; ll read() {ll x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int main() {n=read(),c=read();for(int i=1;i<=n;i++){a[i]=read();m[a[i]]++;maxn=max(maxn,a[i]);} sort(a+1,a+1+n);for(int i=1;i<=n;i++)if(a[i]+c>maxn) break;else ans+=m[a[i]+c];printf("%lld",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/z360/p/7875212.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的洛谷——P1102 A-B数对的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。