【LightOJ 1307 + 二分】
发布日期:2021-11-04 12:59:39
浏览次数:10
分类:技术文章
本文共 1437 字,大约阅读时间需要 4 分钟。
LightOJ 1307
Description
You are given N sticks having distinct lengths; you have to form some triangles using the sticks. A triangle is valid if its area is positive. Your task is to find the number of ways you can form a valid triangle using the sticks.Input
Input starts with an integer T (≤ 10), denoting the number of test cases.Each case starts with a line containing an integer N (3 ≤ N ≤ 2000). The next line contains N integers denoting the lengths of the sticks. You can assume that the lengths are distinct and each length lies in the range [1, 109].
Output
For each case, print the case number and the total number of ways a valid triangle can be formed.Sample Input
3 5 3 12 5 4 9 6 1 2 3 4 5 6 4 100 211 212 121 Sample Output Case 1: 3 Case 2: 7 Case 3: 4#include#include using namespace std;int pa[2011];int main(){ int T,nl = 0,N,i,j,pl,kl,ans; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i = 1 ; i <= N ; i++) scanf("%d",&pa[i]); sort(pa + 1,pa + 1 + N); ans = 0; for(i = 1 ; i <= N -2; i++) for(j = i + 1 ; j <= N -1; j++)//确定两边 { pl = pa[i] + pa[j]; kl = lower_bound(pa + j , pa + 1 + N ,pl) - pa; //二分查找第三边 if(kl == j) continue; ans += kl - j - 1; } printf("Case %d: %d\n",++nl,ans); } return 0;}
转载地址:https://blog.csdn.net/WYK1823376647/article/details/52618126 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年03月30日 13时27分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于SnowFlake算法如何让分库分表中不同的ID落在同一个库的算法的实现
2019-04-27
Linux文件管理参考
2019-04-27
FTP文件管理项目(本地云)项目日报(一)
2019-04-27
FTP文件管理项目(本地云)项目日报(二)
2019-04-27
FTP文件管理项目(本地云)项目日报(三)
2019-04-27
FTP文件管理项目(本地云)项目日报(四)
2019-04-27
【C++】勉强能看的线程池详解
2019-04-27
FTP文件管理项目(本地云)项目日报(七)
2019-04-27
FTP文件管理项目(本地云)项目日报(八)
2019-04-27
【Linux】血泪教训 -- 动态链接库配置方法
2019-04-27
FTP文件管理项目(本地云)项目日报(九)
2019-04-27
以练代学设计模式 -- FTP文件管理项目
2019-04-27
FTP文件管理项目(本地云)项目日报(十)
2019-04-27
学以致用设计模式 之 “组合模式”
2019-04-27
我用过的设计模式(7)--享元模式
2019-04-27
MySQL数据库从入门到实战应用(学习笔记一)
2019-04-27
MySQL数据库从入门到实战应用(学习笔记二)
2019-04-27