题目描述

递增三元组 - 蓝桥云课 (lanqiao.cn)

题目分析

60分解法：

直接暴力循环每一个数进行比较

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll n, a[N], b[N], c[N], ans;
int main()
{cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];for(int i = 1; i <= n; i ++)cin >> b[i];for(int i = 1; i <= n; i ++)cin >> c[i];for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++){for(int k = 1; k <= n; k ++){if(a[i] < b[j] && b[j] < c[k])ans ++;}}}cout << ans;return 0;
}

满分解法：

由于ABC的值是完全独立的所以可以使用乘法原理

由B作为一个判断点，看有多少个A符合要求，再看有多少个C符合要求，最后的答案则为两部分相乘的结果

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll n, a[N], b[N], c[N], s[N], cnt[N];
ll sa[N];//sa[i]表示在a[]中有多少个数小于b[i] 
ll sc[N];//sc[i]表示在c[]中有多少个数大于b[i]
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i], a[i] ++;for(int i = 1; i <= n; i ++)cin >> b[i], b[i] ++;for(int i = 1; i <= n; i ++)cin >> c[i], c[i] ++;//求sa[] for(int i = 1; i <= n; i ++)cnt[a[i]] ++;for(int i = 1; i <= N; i ++)s[i] = s[i - 1] + cnt[i];for(int i = 1; i <= n; i ++)sa[i] = s[b[i] - 1];//求sc[] memset(cnt, 0, sizeof cnt);memset(s, 0, sizeof s);for(int i = 1; i <= n; i ++)cnt[c[i]] ++;for(int i = 1; i <= N; i ++)s[i] = s[i - 1] + cnt[i];for(int i = 1; i <= n; i ++)sc[i] = s[N] - s[b[i]];//枚举每个b[i]ll ans = 0;for(int i = 1; i <= n; i ++)ans += sa[i] * sc[i];cout << ans;return 0;
}