Algoogle

Algorithm for Programming Contest

PKU 3663 Costume Party

Category: PKU Tag: binary-search

Costume Party

問題概要


長さの和がS以下になるペアの組み方の総数を求める

解法


ペアを全て調べるとO(N^2)で間に合わない.
片方の長さlを固定すると, もう片方はS-l以下でなければならない.
よって長さをソートしておいて2分探索でS-l以下で最大のものを探す.
組み合わせなので自分よりあとかつ, 探索結果の位置以前の部分の数が答えに加えられる.

コード


(3663.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <cstdio>

using namespace std;

int N, S;
int len[20010];

int main(){
    scanf("%d%d", &N, &S);
    for(int i = 0; i < N; i++)
        scanf("%d", len+i);
    sort(len, len+N);

    int ans = 0;
    for(int i = 0; i < N; i++){
        if(len[i] > S / 2) break;
        ans += upper_bound(len+i+1, len+N, S-len[i]) - len - i - 1;
    }
    printf("%d\n", ans);
    return 0;
}

Comments