首页 > 代码库 > 【XY1398】孙云球
【XY1398】孙云球
题目大意:
给出$N$个数$a_{1}, a_{2}, ..., a_{N}$,定义三元组$(x,y,z)$满足:
$a_{x}<a_{y}<a_{z}$
$a_{y}-a_{x}≤a_{z}-a_{y}≤2*(a_{y}-a_{x})$
求出这样的三元组的个数
$1≤n≤1000$, $1≤a_{i}≤10^{9}$
算法:二分,STL的妙用
题解:
显然直接枚举会超时(虽然卡过是可以的QWQ)
这题可以用二分来做,但是更简单的方法是用STL中的upper_bound和lower_bound函数可以轻松完成~
上界和下界可以通过不等式推出来哦,两个函数的意思可以自行Baidu,然后就直接看代码吧!
(众:不想解释就直说QAQ)
代码:
#include<cstdio> #include<algorithm> using namespace std; const int N=1005; int a[N],n,ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans += upper_bound(a+1, a+1+n, 3*a[j]-2*a[i]) - lower_bound(a+1, a+1+n, 2*a[j]-a[i]); printf("%d",ans); }
【XY1398】孙云球
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。