C. Random Events(思维+概率)

Problem - 1461C - Codeforces

罗恩是一个长度为n的排列组合的快乐主人。

一个长度为n的排列组合是一个由1到n的n个不同的整数按任意顺序组成的阵列。例如，[2,3,1,5,4]是一个排列组合，但是[1,2,2]不是一个排列组合（2在数组中出现了两次），[1,3,4]也不是一个排列组合（n=3，但是数组中有4）。

罗恩的排列组合要经过m个以下类型的实验：（ri，pi）。这意味着范围[1,ri]中的元素（换句话说，长度为ri的前缀）必须以pi的概率进行升序排序。所有的实验都是按照输入数据中指定的顺序进行的。

作为一个例子，我们来看看一个排列组合[4,2,1,5,3]和一个实验（3,0.6）。在这样一个概率为60%的实验之后，排列组合将变成[1,2,4,5,3]的形式，而概率为40%的排列组合将保持不变。

你必须确定经过m次实验后，排列组合成为完全升序排序的概率。

输入
每个测试包含一个或多个测试案例。第一行包含测试用例的数量t（1≤t≤100）。

每个测试案例的第一行包含两个整数n和m（1≤n,m≤105）--分别是排列组合的长度和实验的数量。

每个测试用例的第二行包含n个整数a1,a2,...,an(1≤ai≤n)--排列组合的内容。

每个测试案例的下面m行分别包含一个整数ri和一个实数pi（1≤ri≤n,0≤pi≤1）--前缀的长度和它被排序的概率。所有的概率都最多给出6位小数。

保证n和m的总和不超过105（∑n,∑m≤105）。

输出
对于每个测试案例，打印一个数字--经过所有实验后，排列组合成为升序排列的概率。如果你的答案的绝对或相对误差不超过10-6，将被认为是正确的。

形式上，让你的答案为a，陪审团的答案为b。你的答案被接受，当且仅当|a-b|max(1,|b|)≤10-6。

例子
输入复制
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
输出拷贝
0.600000
0.720000
0.989500
1.000000
备注
对第一个测试案例的解释。可以证明，最终的排列组合是否被排序完全取决于在(4,0.6)实验中进行的排序。

题解:
非常简单的一道题,主要看能不能理解题意

从后往前找第一个a[i] 不等于i的,因为如果a[i] = i,代表i往后的都已排好序,不需要操作,如果a[i]!=i,ma=  i代表要对前i个进行排序,

剩下就是找前缀大于ma的找不可能的情况(1-y)相乘,最后

1- ans就是可能的概率

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
int a[200505];
int b[200050];
void solve()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	int ma = 0;
	for(int i = 1;i <= n;i++)
	{
		if(a[i]!=i)
		{
			ma = i;
		}
	}
	double ans = 1;
	for(int i = 1;i <= m;i++)
	{
		int x;
		double y;
		cin >> x>>y;
		if(x >= ma)
		{
			ans = ans*(1.0 - y);
		}
	}
	ans = 1.0 - ans;
	if(ma != 0)
	printf("%.8lf\n",ans);
	else
	printf("%lf\n",1.0);
}
signed main()
{
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}