【Codeforces 1461 C】Random Events，贪心，概率统计

problem

C. Random Events
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Ron is a happy owner of a permutation a of length n.

A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Ron’s permutation is subjected to m experiments of the following type: (ri, pi). This means that elements in range [1,ri] (in other words, the prefix of length ri) have to be sorted in ascending order with the probability of pi. All experiments are performed in the same order in which they are specified in the input data.

As an example, let’s take a look at a permutation [4,2,1,5,3] and an experiment (3,0.6). After such an experiment with the probability of 60% the permutation will assume the form [1,2,4,5,3] and with a 40% probability it will remain unchanged.

You have to determine the probability of the permutation becoming completely sorted in ascending order after m experiments.

Input
Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤100).

The first line of each test case contains two integers n and m (1≤n,m≤105) — the length of the permutation and the number of experiments, respectively.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — contents of the permutation.

The following m lines of each test case each contain an integer ri and a real number pi (1≤ri≤n,0≤pi≤1) — the length of the prefix and the probability of it being sorted. All probabilities are given with at most 6 decimal places.

It is guaranteed that the sum of n and the sum of m does not exceed 105 (∑n,∑m≤105).

Output
For each test case, print a single number — the probability that after all experiments the permutation becomes sorted in ascending order. Your answer will be considered correct if its absolute or relative error does not exceed 10−6.

Formally, let your answer be a, and the jury’s answer be b. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6.

Example
inputCopy
4
4 3
4 3 2 1
1 0.3
3 1
4 0.6
5 3
4 2 1 3 5
3 0.8
4 0.6
5 0.3
6 5
1 3 2 4 5 6
4 0.9
5 0.3
2 0.4
6 0.7
3 0.5
4 2
1 2 3 4
2 0.5
4 0.1
outputCopy
0.600000
0.720000
0.989500
1.000000
Note
Explanation of the first test case: It can be demonstrated that whether the final permutation is sorted or not depends solely on sorting being performed in the (4,0.6) experiment.

solution

/*
题意：
+ 给出一个长为n的全排列，执行q次操作，每次对1-ri进行排序，排序的概率为pi，不排的概率为1-pi。求执行完全部操作后序列有序的概率。
思路：
+ 因为每次都是对前缀操作，所以真正可以影响到整个数组的，其实是a[ri],a[ri]大于等于数组都最后不有序的位置相乘，就可以求出1-P。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5;
int a[maxn], b[maxn];
int main(){
	int T;  cin>>T;
	while(T--){
		int n, m;  cin>>n>>m;
		for(int i = 1; i <= n; i++){
			cin>>a[i];  b[i] = a[i];
		}
		sort(b+1,b+n+1);
		int p = n;
		while(p>0 && a[p]==b[p])p--;
		double ans = 1;
		for(int i = 1; i <= m; i++){
			int ri; double pi;
			cin>>ri>>pi;
			if(ri >= p)ans *= (1-pi);
		}
		if(p)printf("%.7lf\n",1-ans);
		else printf("%.7lf\n",1.0);
	}
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/113816594