hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, ... AN],已知其中每个元素Ai的值都只可能是1, 2或者3。

请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak

输入

第一行包含一个整数N

第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)

对于30%的数据,1 ≤ N ≤ 100

对于80%的数据,1 ≤ N ≤ 1000

对于100%的数据,1 ≤ N ≤ 100000

输出

一个整数表示答案

样例输入
6
1 3 2 1 2 3
样例输出
3

给定一个数组,只包含1,2,3这三个数,问数组中有多少个三元组下标(i,j,k),满足a[i]<a[j]<a[k]。

我一开始的想法是,找出所有1,2,3出现的下标,对于每一个1的下标i,去2的下标数组中找一个lowerbound j,然后用j在3的下标数组中找一个lowerbound k,则3的下标数组中k往后的下标都是符合条件的。这需要两层循环,过了90%的数据,然后TLE了。

后来经过大神点拨,要想得到符合条件的三元组,则2一定要在中间,所以我们可以遍历原数组,对于每一个出现的2,用其左边的1的频数乘以其右边3的频数,就是这个2可以构成的合法三元组的个数。

为了不重复计算,我们可以提前算好每个位置左边和右边1和3的频数,到时候直接用left[1]*right[3]就好了。完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;

typedef long long ll;

int main() {
	//freopen("input.txt", "r", stdin);
	int n = 0;
	scanf("%d", &n);
	vector<int> nums(n, 0);
	map<int, int> left, right;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &nums[i]);
		++right[nums[i]];
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		--right[nums[i]];
		if (nums[i] == 2) {
			ans += left[1] * right[3];
		}
		++left[nums[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时18MS。

Leave a Reply

Your email address will not be published. Required fields are marked *