甘肃做网站哪个平台好,郑州东区做网站电话,破解wordpress后台密码,中文网站排名文章目录 题目原题链接思路分析二分做法1二分做法2双指针做法前缀和解法 题目 原题链接
递增三元组
思路分析
由时间复杂度可知需要至少优化到 O ( n l o g n ) O(nlogn) O(nlogn)才行 而纯暴力枚举三个数组的话#xff1a; O ( n 3 ) O(n^3) O(n3) 可以考虑将b[]作为标志 O ( n 3 ) O(n^3) O(n3) 可以考虑将b[]作为标志枚举a[]中小于b[i]的和c[]中大于b[i]的 既然是查找 这种类型的题目可以想到用二分或者双指针来降低枚举的时间复杂度
二分做法1
#include iostream
#include algorithm
using namespace std;
typedef long long LL;
const int N 100010;
int a[N], b[N], c[N];
int n;
bool check_a(int mid, int x) {if(a[mid] x) return true;else return false;
}
bool check_c(int mid, int x) {if(c[mid] x) return true;else return false;
}
int main() {cin 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]);sort(a 1, a 1 n);sort(b 1, b 1 n);sort(c 1, c 1 n);LL res 0;for(int i 1; i n; i) { //以b[]为参照物int st 0, ed 0;int la 1, ra n, lc 1, rc n;while(la ra) {int mid la ra 1 1;if(check_a(mid, b[i])) la mid;else ra mid - 1;}if(a[ra] b[i]) st ra;while(lc rc) {int mid lc rc 1;if(check_c(mid, b[i])) rc mid;else lc mid 1;}if(c[rc] b[i]) ed n - rc 1;res (LL)st * ed;}printf(%lld, res);return 0;
}二分做法2 上方的只需要变动这块就行直接调用库函数 for(int i 1; i n; i) { //以b[]为参照物int st 0, ed 0;int la 1, ra n, lc 1, rc n;// while(la ra) {// int mid la ra 1 1;// if(check_a(mid, b[i])) la mid;// else ra mid - 1;// }// if(a[ra] b[i]) st ra;//要想找第一个小于的那么可用第一个大于等于的-1st lower_bound(a 1, a 1 n, b[i]) - a - 1;// while(lc rc) {// int mid lc rc 1;// if(check_c(mid, b[i])) rc mid;// else lc mid 1;// }// if(c[rc] b[i]) ed n - rc 1;//找第一个大于的可直接用uppered n - (upper_bound(c 1, c n 1, b[i]) - c) 1;res (LL)st * ed;}双指针做法
//双指针只需修改上方为下面这样即可
int l 1, r 1;
for(int i 1; i n; i) {while(an a[l] b[i]) l;while(cn c[r] b[i]) r;ans (LL)(l-1)*(n-r1);
}前缀和解法 #includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N 100010;
int n;
int a[N],b[N],c[N];
int as[N]; //as[N]表示在A[]中有多少个数小于b[i]
int cs[N]; //cs[N]表示在C[]中有多少个数小于b[i]
int cnt[N],s[N]; //s[i]表示1~i之间的数的数量int main()
{cin n;long long res 0;//a,b,c的目的是为了范围从1开始以便后续使用前缀和for(int i 0;i n;i) scanf(%d,a[i]),a[i];for(int i 0;i n;i) scanf(%d,b[i]),b[i];for(int i 0;i n;i) scanf(%d,c[i]),c[i];//求as[i]for(int i 0;i n;i) cnt[a[i]]; //某个数的数量for(int i 1;i N;i) s[i] s[i-1] cnt[i]; //前缀和for(int i 0;i n;i) as[i] s[b[i] - 1]; //1到b[i]之间的数的数量//求cs[i]memset(cnt,0,sizeof cnt); //将cnt重置为0memset(s,0,sizeof s); //将s重置为0for(int i 0;i n;i) cnt[c[i]];for(int i 1;i N;i) s[i] s[i-1] cnt[i];for(int i 0;i n;i) cs[i] s[N-1] - s[b[i]];//枚举每个b[i]for(int i 0;i n;i) res (long long)as[i] * cs[i];cout res endl;return 0;
}
