cqyz oj | 化装晚会加强版 | 二分搜索

Description

　　万圣节又到了！FJ打算带他的奶牛去参加一个化装晚会，但是FJ只做了一套能容下三头总长不超过 S 的牛的恐怖服装。FJ养了 N 头按 1..N 顺序编号的奶牛，编号为 i 的奶牛的长度为 Li。如果三头奶牛的总长度不超过 S，那么她们就能穿下这套服装。
　　FJ想知道，如果他想选择三头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。

Input

　　第 1 行是 2 个用空格隔开的整数 N 和 S;　　接下来有 n 行，每行包含一个整数 L_i，表示奶牛的身长为。

Output

　　仅一行一个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种方案是被视为相同的。

Sample Input 1

5 10
3 2 5 1 7

Sample Output 1

5

Hint

50%的数据满足：1<=n<=500
100%的数据满足：1<=n<=2000，1<=S<=2,000,000,000，1<=L_i<=2,000,000,000

上来先看到的是数据爆int，所以开long long
相比原版化装晚会，牛数由2头变成了3头，不能再用贪心前后指针移动来解决。
但是注意到n的数据量2000，\(O(n^2)\)是安全的，所以可以枚举前两头牛，第三头牛排序后二分搜索，复杂度\(O(n^2logn)\)
(原版化装晚会也可以用这个办法做，时间\(O(nlogn)\)

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

ll L[2005];

int main() {
    ll n,s;
    ll ans=0;

    scanf("%lld%lld",&n,&s);
    for(int i=1; i<=n; i++)
        scanf("%lld",&L[i]);
    sort(L+1,L+1+n);
    for(ll i=1; i<=n; i++) {
        for(ll j=i+1; j<=n; j++) {
            ll q2=L[i]+L[j];
            if(q2<=s) {
                ll p=upper_bound(L+1+j,L+1+n,s-q2)-L;
                ans+=p-j-1;
            }
        }
    }
    printf("%lld",ans);
}

cqyz oj | 化装晚会加强版 | 二分搜索

原文：https://www.cnblogs.com/de-compass/p/11252965.html