C. Random Events(思维)

男娘i 2021-07-16 15:27 335阅读 0赞

[题目][Link 1]

思路：想一想可以发现，如果要让所有的元素排好序，则每个分别都要在自己的位置上。然后我们可以进行的操作是可以让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;
    	}
    }

[Link 1]: https://codeforc.es/contest/1461/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，335人围观）

还没有评论，来说两句吧...

相关阅读

相关 C# 事件（Event）

事件（Event）基本上说是一个用户操作，如按键、点击、鼠标移动等等，或者是一些提示信息，如系统生成的通知。应用程序需要在事件发生时响应事件。例如，中断。 C\ 中使用事件

谁借莪１个温暖的怀抱￠/ 2024年03月22日 23:27/ 0 赞/ 85 阅读

相关 Python常用函数：random【random.random、random.randint、random.choice、random.sample、random.shuffle】

一、random.random()：从0~1之间随机生成一个随机数二、random.randint(int,int)：从2个int之间随机抽取一个样本三、ra

本是古典何须时尚/ 2023年10月05日 22:25/ 0 赞/ 14 阅读

相关 C#——关键字：event

C\——关键字：event event 关键字用于声明发布服务器类中的事件。示例下面的示例演示如何声明和引发使用 EventHandler 作为基础委托类型的

淡淡的烟草味﹌/ 2023年01月03日 01:37/ 0 赞/ 101 阅读

相关 C# Random

c\ Random快速连续产生相同随机数的解决方案 Random类是一个产生伪随机数字的类，它的构造函数有两种，一个是直接New Random()，另外一个是

不念不忘少年蓝@/ 2022年08月11日 05:59/ 0 赞/ 162 阅读

相关 C#中的Event

[点击打开链接][Link 1] 在发生其他类或对象关注的事情时，[类][Link 2]或对象可通过事件通知它们。发送（或引发）事件的类称为“发行者”，接收（或处理）事

我就是我/ 2022年08月10日 13:52/ 0 赞/ 192 阅读

相关 C# 事件（Event）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlbmd5

蔚落/ 2021年12月21日 06:17/ 0 赞/ 343 阅读

相关 C# delegate和C# event

在基于Windows平台的程序设计中，事件（event）是一个很重要的概念。因为在几乎所有的Windows应用程序中，都会涉及大量的异步调用，比如响应点击按钮、处理Window

男娘i/ 2021年12月07日 14:55/ 0 赞/ 289 阅读

相关 C# 随机数生成 Random

随机数类：Random 关键词：`Random` 1. 创建一个随机数对象： `Random r = new Random();` 2. 调用【Next方法】，随机

不念不忘少年蓝@/ 2021年12月03日 02:43/ 0 赞/ 400 阅读

相关 C. Random Events(思维)

[题目][Link 1] 思路：想一想可以发现，如果要让所有的元素排好序，则每个分别都要在自己的位置上。然后我们可以进行的操作是可以让K前k个元素直接排好序，那么我们只需

男娘i/ 2021年07月16日 15:27/ 0 赞/ 336 阅读

相关 C#事件（Event）

事件（`Event`）基本上说是一个用户操作，如按键、点击、鼠标移动等等，或者是一些出现，如系统生成的通知。应用程序需要在事件发生时响应事件。例如，中断。事件是用于进程间通信

╰半夏微凉°/ 2021年06月26日 16:06/ 0 赞/ 547 阅读