解题思路: 1.先排序,再枚举每种情况就行
2.对于双指针,因为题目是要Ai < Bj < Ck, 所以只要找到A小于B的个数和C大于B的个数,用乘法原理得出答案。
参考代码:
(暴力)
#include
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
typedef long long ll;
int main(void) {
ll ans = 0;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n);
sort(b, b + n);
sort(c, c + n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (b[j] > a[i]) {
for (int k = 0; k < n; k++) {
if (c[k] > b[j]) {
ans += (n - k);
break;
}
}
}
}
}
printf("%lld\n", ans);
return 0;
}
(双指针)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
typedef long long ll;
int main(void) {
ll ans = 0;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n);
sort(b, b + n);
sort(c, c + n);
for (int i = 0, j = 0, k = 0; i < n; i++) {
while (j < n && a[j] < b[i]) j++;
while (k < n && c[k] <= b[i]) k++;
ans += (ll)j * (n - k);
}
printf("%lld\n", ans);
return 0;
}
0.0分
1 人评分
WU-printf基础练习2 (C++代码)浏览:2000 |
校门外的树 (C语言代码)浏览:692 |
数对 (C语言代码)浏览:697 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:551 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:629 |
Pascal三角 (C语言代码)浏览:641 |
输入输出格式练习 (C语言代码)浏览:743 |
矩阵转置 (C语言代码)浏览:782 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:455 |
快速排序算法1浏览:877 |