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]就好了。完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时18MS。]]>