AtCoder Regular Contest 084 C - Snuke Festival【二分】

C - Snuke Festival

....最后想到了，可是不应该枚举a[]，这样要二重循环，而应该枚举b[],这样只需一重循环。。。

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e5+10;
 8 int a[maxn],b[maxn],c[maxn];
 9 int n;
10 
11 int FindLastSmaller(int key)
12 {
13     int l=0,r=n-1;
14     while(l<=r){
15         int mid=(l+r)>>1;
16         if(a[mid]>=key) r=mid-1;
17         else l=mid+1;
18     }
19     return r;
20 }
21 
22 int FindFirstLarger(int key)
23 {
24     int l=0,r=n-1;
25     while(l<=r){
26         int mid=(l+r)>>1;
27         if(c[mid]>key) r=mid-1;
28         else l=mid+1;
29     }
30     return l;
31 }
32 
33 int main()
34 {
35     cin>>n;
36     for(int i=0;i<n;i++) cin>>a[i];
37     for(int i=0;i<n;i++) cin>>b[i];
38     for(int i=0;i<n;i++) cin>>c[i];
39     sort(a,a+n);
40     sort(b,b+n);
41     sort(c,c+n);
42     ll ans=0;
43     for(int i=0;i<n;i++){
44         ll p1=FindLastSmaller(b[i]);
45         ll p2=FindFirstLarger(b[i]);
46         ans+=(p1+1)*(n-p2);
47     }
48     cout<<ans<<endl;
49     return 0;
50 }      

lower_bound(),upper_bounder()不能再好用。。。

1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn = 1e5 + 1000;
 8 int a[maxn], b[maxn], c[maxn];
 9 int n;
10 
11 int main()
12 {
13     scanf("%d", &n);
14     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
15     for (int i = 0; i < n; i++) scanf("%d", &b[i]);
16     for (int i = 0; i < n; i++) scanf("%d", &c[i]);
17     sort(a, a + n);
18     sort(b, b + n);
19     sort(c, c + n);
20     ll ans = 0;
21     for (int i = 0; i<n; i++) {
22         ll p = lower_bound(a, a + n, b[i]) - a;
23         ll q = upper_bound(c, c + n, b[i]) - c;
24         ans += p*(n - q);
25     }
26     printf("%lld\n", ans);
27 }      

转载于:https://www.cnblogs.com/zxhyxiao/p/7797200.html