C. A Tale of Two Lands

题目链接:https://codeforces.com/contest/1166/problem/C

题目大意:给你n个点,然后每一次可以选两个不同的点,然后问你有多少对(x,y)满足

min(|x + y|,|x-y |)< = min (|x|,|y|)

max(|x + y|,|x-y |)< = max (|x|,|y|).

具体思路:假设|x| <= |y|

然后分情况讨论.

x>=0,y>=0

x>=0,y<=0

x<=0,y>=0

x<=0,y<=0

最终化简成 |x| <= |y| <= |2*x|.

然后每一次找出小于等于当前值的左边界和大于当前值两倍的右边界+1,把这些值累加.

然后再就是去重的过程 假设4的个数有3个(这个题不可能出现三个的情况,最多两个),然后去重的过程就是 3*3 - c(3,2).

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define ull unsigned long long
 5 # define inf 0x3f3f3f3f
 6 const int maxn = 2e5+100;
 7 vector<ll>Edge;
 8 map<ll,ll>vis;
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     ll tmp;
14     for(int i=1; i<=n; i++)
15     {
16         scanf("%lld",&tmp);
17         Edge.push_back(fabs(tmp));
18         vis[fabs(tmp)]++;
19     }
20     sort(Edge.begin(),Edge.end());
21     ll sum=0;
22     for(auto i: Edge)
23     {
24         int  L=lower_bound(Edge.begin(),Edge.end(),i)-Edge.begin();
25         int R=upper_bound(Edge.begin(),Edge.end(),2ll*i)-Edge.begin();
26         sum+=R-L;
27 //        cout<<L<<" "<<R<<endl;
28     }
29     for(auto i: vis)
30     {
31         sum-=i.second*i.second-i.second*(i.second-1ll)/2ll;
32     }
33     printf("%lld
",sum);
34 }
原文地址:https://www.cnblogs.com/letlifestop/p/10896771.html