递增三元组C++

本文主要是介绍递增三元组C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 题目

 

输入样例：

3
1 1 1
2 2 2
3 3 3

输出样例：

27

思路1 

 题目让我们求所有满足Ai < Bi < Ci的三元组组合，我们可以先将A, B, C三个数组按升序排序，设计分别指向A数组和C数组的指针ia、ic，一开始指向数组的第一个数。对于B数组中的每一个B[i]，利用指针ia，从A数组中找到最后一个小于B[i]的数；利用指针ic，从C数组中找到第一个大于B[i]的数，那么对于特定的一个B[i]，共可以组成ia * 1 * (n - ic)个三元组。随着i的增加，B[i]也会增大，ia、ic只能往后移动……剩下的看代码吧。

代码1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int n;
void input(int arr[])
{for (int i = 1; i <= n; i ++)cin >> arr[i];sort(arr + 1, arr + n + 1);
}int main()
{cin >> n;input(a);input(b);input(c);//三元组总个数可能爆intLL ia = 0, ic = 0, res = 0;for (int i = 1; i <= n; i ++){while (ia < n && a[ia + 1] < b[i]) ia ++;while (ic < n && c[ic + 1] <= b[i])ic ++;res += (ia * (n - ic));}cout << res;return 0;}

思路2

前缀和可以表示一个数组前几项的和。如果数组cnt[i]的含义表示A数组中值为i的个数，那么求cnt的前缀和s[i]，s[i]表示A数组中小于等于i的个数，将i替换成B[i]，则s[ B[i] ]表示A数组中小于等于B [i] 的个数。

代码2

/*
利用前缀和 记录a/c数组中<= 某个数有多少个
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;int b[N];
int cnta[N], cntc[N];int main()
{int n, x;cin >> n;for (int i = 1; i <= n; i ++){cin >> x;//x的最小值为0，为了方便计算前缀和，将x加一cnta[++x]++;}//求s[i]for (int i = 1; i <= N; i ++)cnta[i] += cnta[i - 1];for (int i = 1; i <= n; i ++){cin >> b[i];b[i] ++;}for (int i = 1; i <= n; i ++){cin >> x;cntc[++x]++;}for (int i = 1; i <= N; i ++)cntc[i] += cntc[i - 1];long long res = 0;for (int i = 1; i <= n; i ++){res += ((long long)cnta[b[i] - 1] * (cntc[N] - cntc[b[i]]));}cout << res;return 0;
}

这篇关于递增三元组C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---