列表

详情

NC20221. [JSOI2015]非诚勿扰

描述

【故事背景】 JYY赶上了互联网创业的大潮，为非常勿扰开发了最新的手机App实现单身 大龄青年之间的“速配”。然而随着用户数量的增长，JYY发现现有速配的算法似 乎很难满足大家的要求，因此JYY决定请你来调查一下其中的原因。 
【问题描述】 应用的后台一共有N个女性和M个男性，他们每个人都希望能够找到自己的 合适伴侣。为了方便，每个男性都被编上了1到N之间的一个号码，并且任意两 个人的号码不一样。每个女性也被如此编号。 JYY应用的最大特点是赋予女性较高的选择权，让每个女性指定自己的“如 意郎君列表”。每个女性的如意郎君列表都是所有男性的一个子集，并且可能为空。如果列表非空，她们会在其中选择一个男性作为自己最终接受的对象。 
JYY用如下算法来为每个女性速配最终接受的男性：将“如意郎君列表”中的 男性按照编号从小到大的顺序呈现给她。对于每次呈现，她将独立地以P的概率接受这个男性（换言之，会以1−P的概率拒绝这个男性）。如果她选择了拒绝， App就会呈现列表中下一个男性，以此类推。如果列表中所有的男性都已经呈现， 那么中介所会重新按照列表的顺序来呈现这些男性，直到她接受了某个男性为止。 
显然，在这种规则下，每个女性只能选择接受一个男性，而一个男性可能被多个女性所接受。当然，也可能有部分男性不被任何一个女性接受。 这样，每个女性就有了自己接受的男性（“如意郎君列表”为空的除外）。
现在考虑任意两个不同的、如意郎君列表非空的女性a和b，如果a的编号比b的编号小，而a选择的男性的编号比b选择的编号大，那么女性a和女性b就叫做一对不稳定因素。 由于每个女性选择的男性是有一定的随机性的，所以不稳定因素的数目也是有一定随机性的。JYY希望你能够求得不稳定因素的期望个数（即平均数目）， 从而进一步研究为什么速配算法不能满足大家的需求。

输入描述

输入第一行包含2个自然数N,M，表示有N个女性和N个男性，以及所有女性的“如意郎君列表”长度之和是M。
接下来一行一个实数P，为女性接受男性的概率。
接下来M行，每行包含两个整数a,b，表示男性b在女性a的“如意郎君列表” 中。
输入保证每个女性的“如意郎君列表”中的男性出现切仅出现一次。
1 ≤ N,M ≤ 500,000，0.4 ≤ P < 0.6

输出描述

输出1行，包含一个实数，四舍五入后保留到小数点后2位，表示不稳定因素的期望数目。

示例1

输入: 

5 5
0.5
5 1
3 2
2 2
2 1
3 1

输出: 

0.89

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 224ms, 内存消耗: 20060K, 提交时间: 2019-03-09 18:22:15 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ld long double
 
int n,m,now;
ld p,c[500001],ans,r,w,gl[500001];
 
struct node{
	int x,y;
}a[500001];
 
bool operator < (node u,node v)
{
	return u.x==v.x ? u.y<v.y:u.x<v.x;
}
 
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
 
void add(int u,ld v)
{
	for(;u<=n;u+=u&(-u)) c[u]+=v;
}
 
ld cal(int u)
{
	ld now=0;
	for(;u;u-=u&(-u)) now+=c[u];
	return now;
}
 
int main()
{
	n=read();m=read();cin>>p;
	for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read();
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++)
	{
		if(now!=a[i].x)
		{
			for(register int j=i-1;j && a[j].x==now;j--) add(a[j].y,gl[j]);
			now=a[i].x;r=w=1;
			for(register int j=0;a[i+j].x==now;j++,w*=(1-p));
			w=1.0-w;
		}
		gl[i]=r*p/w;r*=(1-p);
		ans+=gl[i]*(cal(n)-cal(a[i].y));
	}
	printf("%.2lf\n",(double)ans);
	return 0;
}

上一题

© 2024 nowcoder.com