[蓝桥杯 2018 省 B] 递增三元组

一、题目描述

P8667 [蓝桥杯 2018 省 B] 递增三元组

二、问题简析

题目要求：

$$\begin{array}{rl}& 1\le i,j,k\le N\\ & A_i<B_j<C_k\end{array}$$

改变一下，得到

$$\{\begin{array}{l}{A}_i<B_j\\ C_k>B_j\end{array}$$

对于一个确定的 $B_j$，统计所有 $<B_j$ 的 $A_i$ 的数量 cntA，统计所有 $>B_j$ 的 $C_k$ 的数量 cntC，对于该 $B_j$ 解的数量为 cntA * cntC。

---

AC代码

复杂度：$O(NlogN)$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
int ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')    flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag)    ret = -ret;
return ret;
}

const int MAX = 1e5 + 3;
int A[MAX], B[MAX], C[MAX], n; 

int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif

n = quickin();
for (int i = 1; i <= n; i++)
A[i] = quickin();
for (int i = 1; i <= n; i++)
B[i] = quickin();
for (int i = 1; i <= n; i++)
C[i] = quickin();

sort(A + 1, A + 1 + n);
sort(C + 1, C + 1 + n);

ll ans = 0;
for (int i = 1; i <= n; i++)
{
int cntA = lower_bound(A + 1, A + 1 + n, B[i]) - A - 1;
int cntC = C + n - upper_bound(C + 1, C + 1 + n, B[i]) + 1;
ans += (ll)cntA * cntC;
}
cout << ans << endl;

return 0;
}

---

完

原文地址：https://blog.csdn.net/hydrogend/article/details/136526365

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！