夹缝中求和

NC213483. 夹缝中求和

描述

给定一个数组a，以及两个正整数 $x\$ 和 $y\$ ，求取两个数 $a_i\$ 和 $a_j$ $( i<j)\$ ，满足 $x≤a_i+a_j≤y\$ 的取法有多少种？

注：只要两个取法有一个角标不同，则视为两种不同的取法。

输入描述

第一行有三个正整数，，，分别代表数组长度，和的下界和上界。
第二行有个正整数

输出描述

一个整数，代表最后的取法数量。

示例1

输入:

5 2 4
1 4 2 2 1

输出:

说明:

共有以下6种取法：

$i=1，j=3，a_i+a_j=1+2=3\\$
$i=1，j=4，a_i+a_j=1+2=3\\$
$i=1，j=5，a_i+a_j=1+1=2\\$
$i=3，j=4，a_i+a_j=2+2=4\\$
$i=3，j=5，a_i+a_j=2+1=3\\$
$i=4，j=5，a_i+a_j=2+1=3\\$

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 73ms, 内存消耗: 764K, 提交时间: 2021-07-04 16:15:21

#include<bits/stdc++.h>
using namespace std;int n,x,y,a[100010];long long cnt=0;int main(){cin>>n>>x>>y;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);for(int i=0;i<n-1;i++){cnt+=(upper_bound(a+i+1,a+n,y-a[i])-a)-(lower_bound(a+i+1,a+n,x-a[i])-a);}cout<<cnt;return 0;}

上一题

下一题

详情