Skip to content

11382: 【原1382】畅畅的牙签盒

题目

题目描述

author: SamJia 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1382

题目描述

最近畅畅买了一个装牙签的大盒子,可以装S根牙签,他又买了N包牙签,第i个牙签包中有Li个牙签,但是他依旧无chǐ,所以他只能无聊地用牙签来做一些奇怪的事情自娱自乐了。

畅畅想把其中两个牙签包中的牙签放到牙签盒里,当然要保证两个牙签包中牙签总数小于或等于牙签盒的容量。畅畅脑子又瓦特了,他想让你帮他算算一共有多少种不同的取法。

说明

  1. 牙签包选择不考虑顺序问题,即选择(第一包+第三包)和选择(第三包+第一包)是一种取法。

  2. 不同的牙签包可能有相同的牙签数。

输入格式

输入第一行,有二个数字N和S,表示牙签包总数N(2 ≤ N ≤ 100,000)和牙签盒容量S(1 ≤ S ≤ 2,000,000)。

输入第2行到第N+1行,每行一个数字Li(1 ≤ Li ≤ 1,000,000),表示第i包中牙签数量。

输出格式

输出一个整数,表示畅畅可以选择的取法总数。

Sample Input

4 6
2
5
2
1

Sample Output

4

样例解释

选择的两个牙签包可以有4种情况,分别是: 第一包+第三包 第一包+第四包 第二包+第四包 第三包+第四包

Hint

畅畅虽然脑子瓦特了,但他的直觉告诉他可能性太多了,int可能数不过来,long long 应该可以。

yyong119's solution

#include <iostream>
#include <algorithm>
#define MAX_N 100010
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    int n, s;
    cin >> n >> s;
    int a[MAX_N];
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    long long total = 0;
    int back = n - 1;
    for (int i = 0; i < n; ++i) {
        while (a[i] + a[back] > s) --back;
        if (back > i) total += back - i;
            else break;
    }
    cout << total << endl;
    return 0;
}