TomekPhone

作者：叶昊星

关键字

贪心，排序不等式

题目描述

给你$n$个元素，每个元素的权值$a_{i}$和$m$个下标最大为$b_{i}$的从$1$开始标号的数组，要求将每个字母放入某个数组的某个位置，设这个位置的下标为$id_{i}$，且同一个位置上最多只能有一个元素，求$min\{\sum_{1}^{n}id_{i}*a_{i}\}$或无解输出$-1$。

数据范围

$n,a_{i}<=50,b_{i}<=1000$

解法1

易知最后元素占据数组的位置一定是尽量靠前的，即如果所有下标为$x$的位置没有全部占满，那么一定不会有元素占据下标为$x+1$的位置。

利用反证法可说明若不然，则可以将这个元素调整至下标为$x$且没有元素的位置使答案变小。

所以最后元素占据的位置是一定满足存在一个值$lim$使得下标$x<lim$的位置全部占满且下标$x>lim$的位置全部为空。

将这些下标从小到大写出来可以得到数组$C$，原问题变为求$min\{\sum_{1}^{n}a_{i}*C_{P_{i}}\}$，其中$P$为$1-n$的一个排列。根据排序不等式易得将数组a排序之后，排列$P$取$P_{i}=i$时为所求答案。这就做完了本题。

注意需要特判无解的情况。

时空复杂度

$O(nlogn)-O(n)$