【题解】机器人

· · 题解

题解 机器人

首先判断无解：如果有事的成功率为 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;
}