题解：CF1461C Random Events

题目告诉我们有一个序列

a

，那么这个

a

就可以分为两个部分。

第一个部分：

1

k

，这个区间内至少有一个元素排列后位置不一样。

第二个部分：

k + 1

n

，这个区间内所有的数字有序排列后对应的数字位置不变。

明显，只用当

k \le r_i \le n

的情况下进行排列才可以让

a

变得有序。

对于答案，考虑求出所有操作排列都不有序的概率

ans

，那么答案就是

1 - ans

。

特别的：对于序列本来就有序的情况，那么答案就是

1

。

code：

CPP

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int a[100009];
long double ans;

inline void sovel() {
	cin >> n >> m;
	ans = 1;
	k = n + 1;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while(a[k - 1] == k - 1 && k - 1 >= 1) k--;
	k--;
	while(m--) {
		int r;
		long double p;
		cin >> r >> p;
		if(r >= k) {
			ans *= (1 - p);
		}
	}
	if(k == 0)
		cout << 1 << "\n"; 
	else 
		cout << 1 - ans << "\n";
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _T = 1;
	cin >> _T;
	while(_T--) {
		sovel();
	}

	return 0;

}

题解：CF1461C Random Events

文章操作

相关推荐

评论

题解：CF1461C Random Events