9分，站外题

万圣节又到了！FJ打算带他的奶牛去参加一个化妆晚会，但是FJ只做了一套能容下两头总长不超过S（1 ≤ S ≤ 1e6）的奶牛的恐怖服装。FJ养了N（2 ≤ N ≤ 1e5）头按 1~N 顺序编号的奶牛，编号为 i 的奶牛长度为 Li（1 ≤ Li ≤ 1e6）。如果两头奶牛的总长度不超过S，那么他们就能穿下这套服装。

FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案

输入格式第一行，两个整数：N和S。

接下来是N行，每行个整数

输出格式一个整数表示FJ可选择的方案数。

输入/输出例子1 输入：

4 6

输出：

样例解释 4种选择分别为：奶牛1 和奶牛3

奶牛1 和奶牛4

奶牛2 和奶牛4

奶牛3 和奶牛4

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll L[20000005];
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);
}

讨论操作

回复

相关推荐

9分，站外题