递增三元组
题目 递增三元组
思路分析
暴力三重循环 过7/13
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N];
int n;
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];
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(c[k]>b[j] && b[j]>a[i])
cnt++;
}
}
}
cout<<cnt;
return 0;
}
发现总数量和大于它的数量有关
比如b中比a中2大的有3 4 8 （3个） c中比b中3大的有5 7 9（3个） 比4大的有5 7 9（3个） 比8大的有9（1个） 那么数量好像有点关系 如果比8大的也有3个的话 就可以是3*3+3*3+3*3=27个
看a是不太方便的 但可以确定的是 这里是有点关系的
那从中间的b入手
a中比b中3小的有2（1个） c中比3大的有5 7 9（3个） 那么包含3的选项有1*3=3个
a中比b中4小的有2（1个） c中比4大的有5 7 9（3个） 那么包含4的选项有1*3=3个
a中比b中8小的有2 5 6（3个） c中比8大的有9（1个） 那么包含8的选项有3*1=3个
应该是3+3+3=9个
验算一下 235 237 239 245 247 249 289 589 689确实是9个
那么问题就可以转化成
先把各个序列排序 对于每个b 找到比他小的a有几个（cnt1） 比他大的c有几个（cnt2） 经过这个b的方案就是cnt1*cnt2 最后累加各个b的方案数即可
在俩序列里做匹配 嗯 二分或者双指针
二分
双指针
考试时不能调试 要考虑到所有情况确实是有些难度 很多边界问题都是依赖数据报错才发现的 唉
递增三元组
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],b[N],c[N];
int n;
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];
sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);
LL cnt=0;
for(int i=1;i<=n;i++){
int l=0,r=n;
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<b[i])
l=mid;
else
r=mid-1;
}
LL cnta=r;
l=1,r=n+1;
while(l<r){
int mid=l+r>>1;
if(c[mid]>b[i])
r=mid;
else
l=mid+1;
}
LL cntc=n-r+1;
cnt+=cnta*cntc;
}
cout<<cnt;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],b[N],c[N];
int n;
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];
sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);
LL cnt=0;
LL idx_a=0,idx_c=0;
for(int i=1;i<=n;i++){
while(a[idx_a+1]<b[i] && idx_a+1<=n)
idx_a++;
LL cntcur_a=idx_a;
while(c[idx_c+1]<=b[i] && idx_c+1<=n)
idx_c++;
LL cntcur_c=n-idx_c;
cnt+=cntcur_a*cntcur_c;
}
cout<<cnt;
return 0;
}
💬 评论