C. Random Events(思维)

题目

思路：想一想可以发现，如果要让所有的元素排好序，则每个分别都要在自己的位置上。然后我们可以进行的操作是可以让K前k个元素直接排好序，那么我们只需找出最后一个没排好序的元素的位置（后面的元素已经排好序了，可以不用管），然后对于q次操作，对于每一次操作如果它的k大于最后一个没排好序元素的位置则可以使数组变为排好序。那么概率则为1-q次操作中所有能使数组排好序的操作的（1-发生概率）相乘，细节见代码。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<iomanip>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;
int lst[Max];
int ls[Max];
int Mod = 1e9 + 7;

int main()
{
   
	int t;cin >> t;
	while (t--)
	{
   
		int n, m;cin >> n >> m;
		for (int i = 1;i <= n;i++)
		{
   
			cin >> lst[i];
			ls[i] = lst[i];
		}
		sort(ls + 1, ls + 1 + n);
		int ma = 0;
		for (int i = 1;i <= n;i++)
		{
   
			if (lst[i] != ls[i])ma = i;
		}
		double ans = 1;
		for (int i = 1;i <= m;i++)
		{
   
			int a;double b;cin >> a >> b;
			if (a >= ma)
			{
   
				ans *= (1-b);
			}
		}
		ans = 1.0 - ans;
		if (ma == 0)cout << fixed << setprecision(1) << 1 << endl;
		else cout <<fixed<<setprecision(7)<< ans << endl;
	}
}