rockdu
题目描述
A parade of all elephants is to commence soon at the Byteotian zoo.
The zoo employees have encouraged these enormous animals to form a single line, as the manager wills it to be the initial figure of the parade.
Unfortunately, the manager himself came to the parade and did not quite like what he saw - he had intended an entirely different order of the elephants.
Therefore he enforced his ordering, claiming the animals would seem most majestic this way, and made the employees reorder the elephants accordingly.
As a pack of moving elephants can wreak havoc, the employees decided to have them rearranged by swapping one pair at a time. Luckily the animals need not stand next to each other in order to swap positions in the line. Making an elephant move, however, is not as easy as it sounds. In fact, the effort one has to put into it is proportional to the animal's mass. Hence, the effort involved in swapping a pair of elephants of respective masses and
can be estimated by
. What is the minimum effort involved in rearranging the elephants according to manager's will?
Write a programme that:
reads from the standard input the masses of all elephants from the zoo, along with their current and desired order in the line, determines a sequence of elephant swaps leading from the initial to the desired order of animals in the line, such that this sequence minimises the summary effort involved in all the swaps, prints out the summary effort on the standard output.
对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay) 若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。
输入输出格式
输入格式：
The first line of the standard input contains a single integer (
) denoting the number of elephants in the zoo.
We assume that the elephants are numbered from to
to simplify things.
The second line holds integers
(
dla
) separated by single spaces and denoting the masses of respective elephants (in kilogrammes).
The third line of input contains pairwise different integers
(
) separated by single spac…
输出格式：
The first and only line of the standard output should contain a single integer denoting the minimum summary effort involved in reordering the elephants from the order represented by the sequence to the one represented by .
输入输出样例
这道题能做出来也是有一定巧合吧，当天早上才在看第一类斯特林数，其中就讲到了排列和轮换的关系。下午看到这题一眼就认出来了。
我们考虑给定数列和目标数列的关系，我们把1~n的每个数看成一个点，我们把相同位置上给定数列的数向目标数列连边。那么我们得到的一定是一群环。
这时候就可以贪心了，首先每个环有两种可能的最有决策：1、用环内最小的数把整个环换完。2、用全局中最小的数把当前环中最小的数换出去，用这个数代替最小的数完成替换工作，把环中的数都换到目标位置后再把环内的最小数换回来。
这样比较一下两个决策贪心即可。
#include<cstdio>
#include<algorithm>
#define LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e6 + 5, inf = 0x3f3f3f3f;
struct edge {
int v, next;
}e[maxn << 1];
int head[maxn], cnt;
void adde(const int &u, const int &v) {
e[++cnt] = (edge) {v, head[u]};
head[u] = cnt;
}
int n, w[maxn], cost[maxn], num[maxn], des[maxn], tmn = inf, pos;
int trip[maxn], vis[maxn];
LL ans;
void Gans(int u, int mn, LL sum) {
if(u == trip[1]) {
LL ret1 = (tmn + mn) * 2 + 1ll * tmn * (trip[0] - 1) + sum - mn;
LL ret2 = 1ll * mn * (trip[0] - 1) + sum - mn;
if(ret1 < ret2) return (ans += ret1, void());
else return (ans += ret2, void());
}
trip[++trip[0]] = u, vis[u] = 1;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
Gans(v, min(mn, w[u]), sum + w[u]);
}
}
int main() {
scanf("%d", &n);
For(i, 1, n) {
scanf("%d", &w[i]);
if(tmn > w[i]) tmn = w[i], pos = i;
}
For(i, 1, n) scanf("%d", &num[i]);
For(i, 1, n) scanf("%d", &des[i]);
For(i, 1, n) adde(des[i], num[i]);
For(i, 1, n) if(!vis[i])
trip[1] = trip[0] = 0, Gans(i, inf, 0);
printf("%lld", ans);
return 0;
}
没有帐号? 立即注册