Random Events C++
比赛题目 题目统计 全部提交 时间限制：C/C++ 2000MS，其他语言 4000MS
内存限制：C/C++ 256MB，其他语言 512MB
描述
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.
输入描述
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).
输出描述
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.
用例输入 1
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
用例输出 1
0.600000 0.720000 0.989500 1.000000
提示
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.
题目：这是一个充满恶意的东西：
要找一个升序数组的概率
大致意思就是先输入t，循环t次，然后输入n和m代表接下来的数组大小以及案例个数，然后随后就是ai（i=0,1,2,3,...n-1)，换行后输入案例分为index（下标）和rate（概率）意思是在这个index之前的数列有rate的几率变为升序排列，也有1-rate没法变为升序，这里就需要我们先排序知道我们最少需要改变的位置是哪里，就比如输入数列为1，4，3，2，5；排序后就是1，2，3，4，5我们知道我们需要排序在4位置之前，我们只用处理index>=4的情况。
这时候给出了
3 0.6
4 0.4
5 0.1
能够变为升序的可能性就是1-（（1-0.4）*（1-0.1））=0.46或者0.4+（1-0.4）*0.1=0.46(这一种写法有点复杂点，就没写)
所以我们可以知道这个题目很简单的概率就这样写：
AC：
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int aa[n],bb[n]; for(int i=0;i<n;i++){ cin>>aa[i]; bb[i]=aa[i]; } sort(aa,aa+n);//排序是为了知道我们需要找到的下标为多少 int mark=0;
//int mark=n-1;
//while(aa[mark]==bb[mark]&&mark>=1)mark--;//是不是很简洁这个while，很灵性，比for好看多了
for(int i=n-1;i>=0;i--) if(aa[i]!=bb[i]){ mark=i+1; break; } double ans=1; for(int i=0;i<m;i++){ int index; double rate; cin>>index>>rate; if(index>=mark) ans*=(1-rate); } ans=1.0-ans; if(mark) printf(%.6f\n,ans); else cout<<1.000000<<endl; } return 0; }