1s
分析:
Count 好感统计 题目来源 USACO Contest 2008 Jan Bronze 题目大意 给出N 个数A[1..N]，要求输出满足i<j 且Ai+Aj>S 的数对的个数。 考察算法 排序 二分 树状数组 算法一 我们很容易想到一个十分朴素的算法。枚举i 和j，如果满足i<j 且Ai+Aj>S， 那么就ans+1，这个算法显然是正确的。 时间复杂度：O（N2） 空间复杂度：O（N） 期望得分：30 分 算法二 在算法一的基础上，我们知道暴力枚举是会超时的。但有序的数列就不同了。 按递减顺序排序后，避免重复，对于每个数Ai，我们只在序号大于i 的数中寻 找。枚举i，若Ai+Ai+1<=S 则直接break，否则二分查找序号大于i 的数中最 后一个满足Ai+Aj>S 的j，如何计算就不用说了。 时间复杂度：O（NlogN） 空间复杂度：O（N） 期望得分：100 分 算法三在算法一的基础上，我们可以将数据先进行有序化，这样统计起来就会比较方 便。我们还可以发现满足i<j 且Ai+Aj>S 的数对个数和满足i<j 且Ai+Aj≤S的数对个数是互补的。我们可以通过求出满足i<j 且Ai+Aj≤S 数对的个数来间接求出问题的解。由Ai+Aj≤S，我们可以得到Aj≤S-Ai，也就是说在数列A[1..N]中满足≤S-Ai 的数都可以成为Aj。那么我们只要查找出S-Ai 在数列中的位置就可以很快统计出与Ai 配对的数。由于A[1..N]已经经过排序，我们通过二分查找就可以很快找出S-Ai 的位置p，此时只需要将ans+p。还需要注意一点，Ai 可能被重复算进去，如果满足2*Ai≤S 我们需要ans-1。当然通过上述过程算出来的ans 是无序数对的个数，最后问题的结应该是N*(N-1)/2-ans/2。当然不能忘记数据类型需要使用int64。
时间复杂度：O（NlogN） 空间复杂度：O（N） 期望得分：100 分 算法四 算法三其实提供了我们另一种思路。我们设C[k]表示数k 在数列A[1..N]中出 现的次数。同算法三，我们先计算满足Ai+Aj≤S 的数对的个数。那么对于每 一个Ai，可以和Ai 配对的书的个数就是ΣC[1..S-Ai]。 可以注意到ΣC[1..S-Ai]是一个求和的过程，显然我们不能朴素枚举。这时候 我们自然会想到用树状数组来优化，用树状数组可以将求和的时间降到logN。 接下来的步骤和算法三是一样的。 时间复杂度：O（NlogS） 空间复杂度：O（N+S） 期望得分：100 分 代码:#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200000+5; int n,s; int a[maxn]; long long cnt=0; int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;i++) { if(a[i]+a[n]<=s) continue; int t=lower_bound(a+i+1,a+n+1,s-a[i]+1)-a; cnt=cnt+n-t+1; } printf("%lld\n",cnt); return 0; } #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } int n,s,a[200005]; long long ans=0; int Find(int x) { int Left=x+1,Right=n; while(Left<Right) { int mid=(Left+Right)/2; if(a[mid]+a[x]>s)Right=mid; else Left=mid+1; } return Left; } int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); n=Get_Int(); s=Get_Int(); for(int i=1; i<=n; i++)a[i]=Get_Int(); sort(a+1,a+n+1); for(int i=1; i<=n; i++) { int pos=Find(i); if(pos<=n&&pos>i&&a[pos]+a[i]>s)ans+=n-pos+1; } printf("%lld\n",ans); return 0; } 另附上Pascal代码: count_排序二分1:
program sdf; const maxn=200005; var a:array[0..maxn] of longint; n,s,ans:int64; procedure openf; begin assign(input,'count.in'); reset(input); assign(output,'count.out'); rewrite(output); end; procedure closef; begin close(input); close(output); end; procedure qsort(l,r:longint); var i,j,t,m:longint; begin i:=l; j:=r; m:=a[random(r-l+1)+l]; repeat while a[i]<m do inc(i); while a[j]>m do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; procedure init; var i:longint; begin readln(n,s); for i:=1 to n do read(a[i]); end; function find(l,r,x:longint):longint; var m:longint; begin while l<=r do begin m:=(l+r) shr 1; if (a[m-1]<=x)and(a[m]>x) then exit(m-1); if a[m]>x then r:=m-1 else l:=m+1; end; exit(0); end; procedure main; var i,p:longint; begin ans:=0; a[n+1]:=s+1; for i:=1 to n do begin if a[i]>=s then continue; p:=find(1,n+1,s-a[i]); ans:=ans+p; if a[i]*2<=s then dec(ans); end; ans:=n*(n-1) shr 1-ans div 2; writeln(ans); end; begin randomize; openf; init; qsort(1,n); main; closef; end. count_排序二分2: program sdf; const maxn=200005; var a:array[1..maxn] of longint; n,s,num:longint; procedure openf; begin assign(input,'count.in');reset(input); assign(output,'count.out');rewrite(output); end; procedure closef; begin close(input);close(output); end; procedure qsort(l,r:longint); var i,j,t,m:longint; begin i:=l;j:=r; randomize; m:=a[random(r-l+1)+l]; repeat while a[i]>m do inc(i); while a[j]<m do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; procedure init; var i:longint; begin readln(n,s); for i:=1 to n do read(a[i]); qsort(1,n); end; function find(x,k:longint):longint; var l,r,mid,t:longint; begin l:=k;r:=n; t:=s-x; repeat mid:=(l+r) shr 1; if a[mid]>t then l:=mid+1 else r:=mid-1; until (a[mid]>t) and (a[mid+1]<=t); exit(mid); end; procedure main; var i,x:longint; ans,t:int64; begin ans:=0; a[n+1]:=-maxlongint; for i:=1 to n-1 do if a[i]+a[i+1]<=s then break else begin x:=find(a[i],i+1); t:=x-i; ans:=ans+t; end; writeln(ans); end; begin openf; init; main; closef; end. count_树状数组: program count; const fname='count'; maxn=200005; maxs=200005; var c:array[1..maxs]of int64; a:array[1..maxn]of longint; n,s,ans:int64; procedure openf; begin assign(input,fname+'.in'); reset(input); assign(output,fname+'.out'); rewrite(output); end; procedure closef; begin close(input); close(output); halt; end; function Lowbit(k:longint):longint; begin Lowbit:=k and -k; end; procedure Add(k:longint); begin while k<=s do begin inc(c[k]); inc(k,Lowbit(k)); end; end; function Sum(k:longint):int64; begin Sum:=0; while k>0 do begin Sum:=Sum+c[k]; dec(k,Lowbit(k)); end; end; procedure init; var i:longint; begin readln(n,s); for i:=1 to n do begin read(a[i]); Add(a[i]); end; readln; end; procedure calc; var i:longint; begin ans:=0; for i:=1 to n do begin if a[i]<s then ans:=ans+Sum(s-a[i]); if a[i]*2<=s then dec(ans); end; ans:=ans div 2; ans:=n*(n-1) div 2-ans; end; procedure print; begin writeln(ans); end; begin openf; init; calc; print; closef; end. 关于树状数组的一些补充: 树状数组虽然不在NOIP 的考察范围之内，但它作为一种简单高效的数据结构可以在许多 题目中占有重要地位。并且树状数组对于求和的操作更是以简单高效著称，它比线段树等其 他高级数据结构常数小了许多。
