自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:16:37，当前版本为作者最后更新于2020-01-25 10:18:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解 机器人

首先判断无解：如果有事的成功率为 $0$，那么输出 Impossible。

否则，我们考虑如何计算某种顺序下的期望花费。

$$\begin{aligned}E&=(1-p_1)(w_1+E)+p_1(1-p_2)(w_1+w_2+E)+\cdots\\&+p_1p_2\cdots p_{n-1}(1-p_n)(w_1+w_2+\cdots+w_n+E)\\&+p_1p_2\cdots p_n(w_1+w_2+\cdots+w_n)\\&=(1-p_1p_2\cdots p_n)E+(w_1+p_1w_2+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n)\end{aligned} $$

从而

$$E=\dfrac{w_1+p_1w_2+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n}{p_1p_2\cdots p_n} $$

我们考虑交换第一件事与第二件事。

$$E^\prime=\dfrac{w_2+p_2w_1+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n}{p_1p_2\cdots p_n} $$

如果 $E^\prime<E$，那么 $w_2+p_2w_1<w_1+p_1w_2$，即 $w_2(1-p_1)<w_1(1-p_2)$，即 $\dfrac {w_2}{1-p_2}<\dfrac{w_1}{1-p_1}$。

对于其他的编号相邻的两件事，同理可得交换后期望花费变小等价于 $\dfrac w{1-p}$ 反序，因此最小值必定在 $\dfrac w{1-p}$ 升序时取到（情况有限故最小值存在，除了它都不是极小的，因此它是最小的）。

$\texttt{code:}$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

struct thing{int id;ll w,p;}a[200005];
bool operator<(thing a,thing b){return a.w*(10000-b.p)<b.w*(10000-a.p);}
int n;
int main()
{
	cin>>n;
	F(i,1,n) a[i].id=i;
	F(i,1,n) rd(a[i].w);
	F(i,1,n) {rd(a[i].p);if(a[i].p==0) {puts("Impossible");return 0;}}
	sort(a+1,a+n+1);
	F(i,1,n) printf("%d ",a[i].id);
	return 0;
}