题目链接:http://codeforces.com/problemset/problem/1166/C

题目大意

  给定 n 个数,任选其中两个数 x,y,使得区间 [min(|x - y|, |x + y|), max(|x - y|, |x + y|)] 能完全盖过区间 [min(|x|, |y|), max(|x|, |y|)],请问一共有多少种选法?

分析

  先随便举个例子,比如 |x| = 3, |y| = 5,可以发现,不管是 [3, 5],还是 [-3, 5], [3, -5], [-3, -5], [min(|x - y|, |x + y|), max(|x - y|, |x + y|)] 都是 [2, 8],因此,负数对答案没有任何影响。
  不妨设 x <= y,若要 [y - x, x + y] 覆盖 [x, y],则必有 2*x >= y。这就很明显了,排完序之后对于每个数二分查找即可。

代码如下

 #include <bits/stdc++.h>
using namespace std; #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i)
#define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define LOWBIT(x) ((x)&(-x)) #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a))
#define msM(a) memset(a,-1,sizeof(a)) #define MP make_pair
#define PB push_back
#define ft first
#define sd second template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
in >> p.first >> p.second;
return in;
} template<typename T>
istream &operator>>(istream &in, vector<T> &v) {
for (auto &x: v)
in >> x;
return in;
} template<typename T1, typename T2>
ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
out << "[" << p.first << ", " << p.second << "]" << "\n";
return out;
} inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
typedef unsigned long long uLL;
typedef pair< double, double > PDD;
typedef pair< int, int > PII;
typedef pair< string, int > PSI;
typedef set< int > SI;
typedef vector< int > VI;
typedef map< int, int > MII;
typedef pair< LL, LL > PLL;
typedef vector< LL > VL;
typedef vector< VL > VVL;
const double EPS = 1e-;
const LL inf = 0x7fffffff;
const LL infLL = 0x7fffffffffffffffLL;
const LL mod = 1e9 + ;
const int maxN = 2e5 + ;
const LL ONE = ;
const LL evenBits = 0xaaaaaaaaaaaaaaaa;
const LL oddBits = 0x5555555555555555; LL n, a[maxN], ans; int main(){
INIT();
cin >> n;
Rep(i, n) {
cin >> a[i];
if(a[i] < ) a[i] = -a[i];
}
sort(a, a + n, greater< int >()); rFor(i, n - , ) {
LL tmp = lower_bound(a, a + i, * a[i], greater< int >()) - a;
ans += i - tmp;
}
cout << ans << endl;
return ;
}

最新文章

  1. SQL Server 自动化运维系列
  2. PHP中json_encode后中文乱码的解决方案
  3. 常用类String的方法
  4. Android单元测试与模拟测试详解
  5. http://bbs.tianya.cn/post-stocks-1665898-1.shtml
  6. 查看/修改 Linux 时间和时区
  7. 黑马程序员+Winform基础(上)
  8. SELinux入门
  9. MYSQL将表名称修改成大写的存储过程
  10. 显示当前一个礼拜的日期 new Date()
  11. UVA 1484 - Alice and Bob&amp;#39;s Trip(树形DP)
  12. codeforces 687C - The Values You Can Make 简单dp
  13. CLR Profiler 性能分析工具
  14. 我的第一个python web开发框架(9)——目录与配置说明
  15. centos7 安装远程桌面
  16. Ocelot简易教程(二)之快速开始1
  17. svgalib_1.4.3 移植
  18. 《Linux课本》读书笔记 第四章
  19. MVC、MVP和MVVM浅谈
  20. Playing FPS Games with Deep Reinforcement Learning

热门文章

  1. 【LeetCode 10】正则表达式匹配
  2. Makefile中的函数
  3. 命令行启动tomcat
  4. 2018 ECNA Regional Contest J. Watch Where You Step
  5. Java文件系统
  6. DQL 数据查询语言 select
  7. certbot免费证书
  8. Zabbix监控搭建
  9. .net 委托 +lamda表达式
  10. git 和github简介