資源限制

時(shí)間限制：1.0s 內(nèi)存限制：256.0MB

題目描述

給定三個(gè)整數(shù)數(shù)組
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]侄泽，
請(qǐng)你統(tǒng)計(jì)有多少個(gè)三元組(i, j, k) 滿足：

1. 1 <= i, j, k <= N
2. Ai < Bj < Ck

輸入格式

第一行包含一個(gè)整數(shù)N飒泻。
第二行包含N個(gè)整數(shù)A1, A2, ... AN。
第三行包含N個(gè)整數(shù)B1, B2, ... BN五督。
第四行包含N個(gè)整數(shù)C1, C2, ... CN。

對(duì)于30%的數(shù)據(jù)，1 <= N <= 100
對(duì)于60%的數(shù)據(jù)，1 <= N <= 1000
對(duì)于100%的數(shù)據(jù)，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

輸出格式

一個(gè)整數(shù)表示答案

樣例輸入

3
1 1 1
2 2 2
3 3 3

樣例輸出

27

閑話：

我先暴力試試谭贪。

#include <stdio.h>
const int maxn = 100001;
int n;
int a[maxn];
int b[maxn];
int c[maxn];
int sum = 0;

int main() {
    
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(a[i] < b[j]) {
                for(int k = 1; k <= n; k++) {
                    if(b[j] < c[k]) {
                        sum ++;
                    }
                }
            }
        }
    }
    
    printf("%d", sum);
    
    return 0;
}

評(píng)測(cè).png

效果還真不錯(cuò)……

思路：

一開始呢境钟，我打算排個(gè)序，然后枚舉a[i]俭识，并在其中枚舉b[j]慨削，找到第一個(gè)使b[j] > a[i]的j。再如法炮制b[i]和c[j]。最后再經(jīng)過復(fù)雜的相乘累加……
后來(lái)發(fā)現(xiàn)缚态，我可以直接枚舉b[i]磁椒，然后在a中找到一個(gè)a[j] < b[i] && a[j+1] >= b[i]，在c中找到一個(gè)c[k]使c[k] > b[i] && c[k-1] <= b[i]玫芦。
對(duì)于每一個(gè)b[i],它可能的遞增三元組數(shù)量就是j * (n - k + 1)浆熔。
ok，代碼如下：

AC：

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 100001;
int n;
int a[maxn];
int b[maxn];
int c[maxn];
long long sum = 0;

bool cmp(int a, int b) {
    return a < b;
}

int main() {
    
    scanf("%d", &n);
    for(int i = 1; i < n+1; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i < n+1; i++) {
        scanf("%d", &b[i]);
    }
    for(int i = 1; i < n+1; i++) {
        scanf("%d", &c[i]);
    }
    
    sort(a+1, a+n+1, cmp);
    sort(b+1, b+n+1, cmp);
    sort(c+1, c+n+1, cmp);
    
    int j = 1;
    int k = 1;
    
    for(int i = 1; i < n+1; i++) {
        while(a[j] < b[i] && j <= n) {
            j++;
        }
        while(c[k] <= b[i] && k <= n) {
            k++;
        }
        
        sum += (long long)(j - 1) * (n - k + 1);
    }
    
    printf("%lld", sum);
    
    return 0;
}

小細(xì)節(jié)：

為了通過最后一個(gè)測(cè)試……
首先桥帆，j和k每次不必從頭開始医增，因?yàn)閎是遞增的。
然后每次sum右邊都要變數(shù)據(jù)類型老虫，因?yàn)樵谥型具@個(gè)結(jié)果就已經(jīng)讓int承受不住了叶骨。