即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Problem 1 好感统计

编程语言 huihao123456 12℃ 0评论
背景
WZOI 的人气越来越高,越来越多的人想要来参加。。。。。。
问题描述
这一天有个人来机房,准备加入WZOI。但是CJH 教练不在,出题考察他们的任务就交给你了。正好你最近遇到了一道有趣的题目,于是你想用这道题目考考这个人,看他是否有能力加入WZOI。
这个问题是这样的,有同一学校的N 个女生要去参加一次舞蹈比赛。这个舞蹈比赛是两人组队的,并且每个学校有且能有一组参加。然后舞蹈教练要从中选出2 个人来参加这次比赛,但并不是任意两个人都能组队参加比赛的。教练给每一位女生打了一个好感度Ai,两个女生能够组队当且仅当她们的好感度之和大于S。也就是说如果两个女生i,j
的Ai+Aj>S,那么她们可以组队。教练想知道总共有多少种组
队方式?当然,你在告诉他这个问题之前,你自己也需要知道答案,于是你准备编程将它算出来。。。
输入格式
输入数据第一行包含两个整数N,S(用一个空格隔开),具体意义见题目描述;
第二行包含N 个整数A1,A2, …,
AN,Ai 表示第i 个女生的好感度。
输出格式
输出数据有且只有一行,包含一个整数M,表示组队方案总数。
样例输入输出
Sample #1
count.in 
5 6
2 3 5 4 2


count.out 
5
Sample #2
count.in 
6 9
2 7 2 5 6 1


count.out 
3
数据规模
对于10%的数据,N≤100,S≤10;
对于30%的数据,N≤1000,S≤100;
对于50%的数据,N≤50000,S≤50000;
对于100%的数据,N≤200000,S≤200000;
对于100%的数据,1≤Ai≤200000。
时间限制

1s




分析:


Count 好感统计
题目来源 USACO Contest 2008 Jan Bronze
题目大意 给出N 个数A[1..N],要求输出满足iS 的数对的个数。
考察算法 排序 二分 树状数组
算法一


我们很容易想到一个十分朴素的算法。枚举i 和j,如果满足iS,那么就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 分

算法三 

在算法一的基础上,我们可以将数据先进行有序化,这样统计起来就会比较方 便。我们还可以发现满足iS 的数对个数和满足i的数对个数是互补的。我们可以通过求出满足i间接求出问题的解。由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
#include
#include
#include
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
#include
#include
#include
#include
#include
#include
#include
#include
#include
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(Lefts)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 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 ix) 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]j;
  if it 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]



关于树状数组的一些补充:

树状数组虽然不在NOIP 的考察范围之内,但它作为一种简单高效的数据结构可以在许多
题目中占有重要地位。并且树状数组对于求和的操作更是以简单高效著称,它比线段树等其
他高级数据结构常数小了许多。











转载请注明:CodingBlog » Problem 1 好感统计

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情