题目链接

https://vjudge.net/contest/413174#problem/C

解题思路

思维吧。
是不是有人没看懂题QWQ，看我题解，会讲解一个样例
大致思路：
从后往前找到第一个不符合自己位置的数现在所在的位置。
对于每一次实验，若输入的数比记录的位置小，是否改成有序，都无所谓，因为要想整个序列变得有序，必须要把无序的部分一次性改完才行；否则，这次实验可以把序列变得有序，为了方便解释，我们拿题目给的第三个样例讲解一下，很显然，这个序列前三个的顺序错了，所以小于3的改不改无所谓，我们完全可以忽略（2，0.4）这组实验，进行第一次实验（4，0.9），修改成功的概论为0.9，所以ans+=0.9；第二次实验（5，0.3），修改成功的概论为 “第一次失败且第二次成功” 的概论 + “第一次成功” 的概论，但是 “第一次成功” 的概论我们加过了，所以只用加上 “第一次失败且第二次成功” 的概论，即0.1 * 0.3，ans+=0.03；第三次实验pass，本质为ans乘1；第四次实验（6，0.7），只需要加上， “第一次失败且第二次失败且第四次成功” 的概论；……。不完全归纳能得到，每次ans要加上的概论为前i-1次有效实验都失败的概论 * 第i次成功的概论。
注意特殊情况的判断，当序列已经排好序的时候，直接输出1。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int main()
{
    int t,a[N],pos,n,m;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof a);pos=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=n;i>=1;i--) if(a[i]!=i) {pos=i;break;}
        double ppp=1,pp=0,p,ans=0;
        int x;
        while(m--)
        {
            cin>>x>>p;
            if(x<pos) continue;
            ans+=ppp*(1-pp)*p;
            ppp*=(1-pp);
            pp=p;            
        }
        if(pos) cout<<ans<<endl;
        else puts("1.0");
    }    
    return 0;
}

总结

半小时A掉，比b题做得还快……
感觉还是cf的样例人性化，样例给的多，而且特殊情况有时候也能给点，牛牛能不能向cf学习一下啊，别封我号啊QWQ