给你一个长度为n的序列A，你需要算出有多少个三元组(Ai，Aj,Ak)满足i<j<k且AiAj
Ak。
[编程题]三元组
- 热度指数：1183 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行一个整数n，表示序列A的长度。
接下来一行n个整数，第i个数表示Ai的值。
输出描述:
一个整数x，表示满足要求的三元组数量。
示例1
输入
6 2 3 5 4 3 3
输出
6
说明
第1个数据为样例。
第2~4个数据范围：
n<=500，Ai<=1000000
第5~7个数据范围：
n<=2000，Ai<=1000000
第8~10个数据范围：
n<=100000，Ai<=1000000
这个题我真的服了，10个测试用例只有一个是示例中按空格分隔数组的格式，还有9个都是把数组换行输入的，对于我这种喜欢用缓冲流读取数据的考生真是神坑，只能用Scanner了
这个题思路不是很难，主要就是遍历数组，让数组中的元素挨个成为三元组的中间元素，然后用二分法寻找小于等于它和大于等于它的数，构成单调不减的三元组。
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Integer> used = new ArrayList<>(); // 已使用数据
ArrayList<Integer> standby = new ArrayList<>(); // 待使用数据
int[] arr = new int[n + 1];
for(int i = 0; i < n; i++) {
arr[i + 1] = sc.nextInt();
if(i == 0)
used.add(arr[i + 1]);
else
standby.add(arr[i + 1]);
}
Collections.sort(standby);
long res = 0L;
for(int i = 2; i <= n; i++){
// 以arr[i]作为中间数
int minIdx = upper_bound(used, arr[i]); // 从小索引的数据中找到第一个大于arr[i]的位置
int maxIdx = lower_bound(standby, arr[i]); // 从大索引的数据中找到第一个大于等于arr[i]的位置
long count1 = minIdx; // minIdx前面的数都可以作为三元组的最小数
long count2 = standby.size() - maxIdx - 1; // maxIdx后面的数都可以作为三元组的最大数
res += count1 * count2; // 累加上以arr[i]为中间数时的三元组数
used.add(minIdx, arr[i]);
standby.remove(maxIdx);
}
System.out.println(res);
}
private static int lower_bound(ArrayList<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
int res = right + 1;
while(left <= right){
int mid = (left + right) >> 1;
if(list.get(mid) >= target){
right = mid - 1;
res = mid;
}else{
left = mid + 1;
}
}
return res;
}
private static int upper_bound(ArrayList<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
int res = right + 1;
while(left <= right){
int mid = (left + right) >> 1;
if(list.get(mid) > target){
right = mid - 1;
res = mid;
}else{
left = mid + 1;
}
}
return res;
}
}
编辑于 2021-09-03 13:24:05
回复(3)
import java.io.*;
public class Main{
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int n= Integer.parseInt(br.readLine());
int[] arr=new int[n];
String[] sp=br.readLine().split(" ");
for (int i = 0; i <n ; i++) {
arr[i]=Integer.parseInt(sp[i]);
}
int ans= process(3,0,Integer.MAX_VALUE,arr);
System.out.println(ans);
}
public static int process(int rest , int i , int preChose , int[] arr){
if (rest==0){
return 1;
}
if (i>=arr.length){
return 0;
}
if (preChose!=Integer.MAX_VALUE&& preChose>arr[i]){
return 0;
}
int res=0;//返回的答案
int p1=process(rest-1,i+1,arr[i],arr);
int p2=process(rest,i+1,preChose,arr);
res=p1+p2;
return res;
}
}
发表于 2022-02-03 20:16:53
回复(2)
先上一个70分代码，复杂度n^2
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,ans=0,a[100005],dp[100005];
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
for(j=i-1;j>=1;j--)
{/**<暴力检查a[i]左侧有多少个比a[i]小的，这个数字记录在dp[i],
dp存储的是以i为的第二个元素的二元组个数 */
if(a[j]<=a[i])
dp[i]++,ans+=dp[j];/**< 顺路计算a[i]左侧a[j]的二元组，这些二元组和a[i]可以构成三元组 */
}
}
cout<<ans;
return 0;
}
可优化的就是内层循环，由于题目ai数据范围为1000000，考虑用树状数组存储和查询比a[i]小元素个数，用另一个树状数组存储二元组个数. #include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,t1[1000005],t2[1000005],ans=0,a[100005];
void add1(int x,int y)
{
for(;x<=1000000;x+=x&-x)
t1[x]+=y;
}
ll get1(int x)
{
ll an=0;
for(;x;x-=x&-x)
an+=t1[x];
return an;
}
void add2(int x,int y)
{
for(;x<=1000000;x+=x&-x)
t2[x]+=y;
}
ll get2(int x)
{
ll an=0;
for(;x;x-=x&-x)
an+=t2[x];
return an;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
int i,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];/**< a1为a[i]左侧不大于它的元素个数，a2为a[i]左侧二元组的个数 */
ll a1=get1(a[i]),a2=get2(a[i]);
add2(a[i],a1);/**< a1个元素和a[i]构成二元组，存储到t2数组 */
add1(a[i],1);/**< 把a[i]值存储在t1数组，用于后序查询 */
ans+=a2;
}
cout<<ans;
return 0;
}
发表于 2021-10-08 20:40:51
回复(0)
思路是 遍历 nums[i], 比nums[i] 小的有s个，比nums[i]大的有l个
ans += s * l 就行了
最后3个例子答案太大溢出了变成负数
long ans = 0;
ans += long (s) * long(l)
最后还是负数，有谁知道怎么解决吗
发表于 2023-08-05 15:41:54
回复(1)
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
LinkedList<Integer> trank = new LinkedList<>();
int[] nums = new int[n];
for (int i = 0; i < n; i++)
nums[i] = in.nextInt();
backtrank(nums,0,trank);
System.out.println(res);
}
static int res = 0;
static void backtrank(int[] nums, int start,LinkedList<Integer> trank){
if((trank.size() + nums.length - start ) < 3)
return;
if(trank.size() == 2){
if(trank.get(0) > trank.get(1))
return;
}
if(trank.size() == 3) {
if (trank.get(0) <= trank.get(1) && trank.get(1) <= trank.get(2)) {
res++;
}
return;
}
if(trank.size() > 3)
return;
for (int i = start; i < nums.length; i++) {
trank.addLast(nums[i]);
backtrank(nums,i + 1,trank);
trank.removeLast();
}
}
}
超时了 只会回溯的方法 后面的用例太大了
发表于 2022-09-12 19:36:46
回复(0)
利用归并排序来辅助完成
#include <iostream>
#include <vector>
using namespace std;
struct Data{
//值
int val;
//左边比他小的
int lsmall;
//右边比他大的
int rbig;
Data():val(0), lsmall(0), rbig(0){}
};
void merge(vector<Data> &v, int l, int m, int r){
int i = l, j = m + 1;
vector<Data> help(r - l + 1);
int small = 0;
int index = 0;
while (i <= m && j <= r){
if (v[i].val <= v[j].val){
v[i].rbig += (r - j + 1);
help[index++] = v[i];
++i;
++small;
}else{
v[j].lsmall += small;
help[index++] = v[j];
++j;
}
}
while (i <= m){
help[index++] = v[i++];
}
while (j <= r){
v[j].lsmall += small;
help[index++] = v[j];
++j;
}
for (index = 0; index < (int)help.size();){
v[l++] = help[index++];
}
}
void f(vector<Data> &v, int l, int r){
if (l >= r){
return;
}
int mid = l + ((r - l) >> 1);
f(v, l, mid);
f(v, mid + 1, r);
merge(v, l, mid, r);
}
void f(vector<Data> &v){
if (v.size() < 2){
return;
}
f(v, 0, v.size() - 1);
}
using ll = long long;
int main(){
int n;
cin >> n;
vector<Data> v(n);
for (int i = 0; i < n; ++i){
cin >> v[i].val;
}
f(v);
ll ans = 0;
for (Data elem : v){
ans += (ll)elem.lsmall * elem.rbig;
}
cout << ans << endl;
return 0;
}
发表于 2021-11-29 14:07:27
回复(0)
问题信息
通过挑战的用户
-
2023-03-07 00:46:26 -
2022-11-07 23:05:45
-
2022-10-03 16:32:31 -
2022-09-16 16:28:42
-
2022-09-14 13:50:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
