娱乐 每 日 算 法 挑 战 【第10期】

[Mr.K 018]

惊了！！！这个没人看的系列居然能初到第10期！！！！！！

今天扒一道贪心题好了：

第10期 最喜欢的“硬菜”

 

题目描述：

        "华瑞世纪”程序设计竞赛圆满结束了，由于PQ God赛前庄严承诺"良乡小学二队”不夺冠，他就请吃饭（虽然夺冠也得请吃饭），没想到帅气迷人的人生赢家会长大人实力太强，单刷7题怒拿冠军，PQ不得不兑现承诺......

        集训队众对"硬菜”都有着自己独到的见解，每个人都点了一道菜，不一会，菜便上齐了，众人便开始动筷（不科学），由于桌子是可以旋转的，每个人便等着自己最喜欢的菜转到自己前面（当然不一定是自己点的菜啊），然后......（自行脑补）

        可怜的hybest等了很久，他最喜欢的菜也没转到自己面前，便默默念想，至少旋转多少次，每个人才能吃到自己喜欢的菜。

输入：

有若干组数据输入，
每组数据中第一行为一个整数n(1<n<10^6)，
接下来有n个数，ai代表刚上完菜时第i个人面前放的是第ai个人最喜欢吃的菜。

输出：

对于每一组数据，输出桌子至少旋转的次数。

 

样例输入：

6
1 2 3 4 5 6
5
1 1 1 1 1
5
1 2 4 3 5

样例输出：

0
4
2

 

本题目是2014年出的题，当时某比赛貌似还叫这个名字，现在这个比赛已经至少改过两次名字和一次赞助商了。

召唤阵：

@yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

四月 20, 2020，由Mr.K 018修改

[yhz012]

看最后一个样例是可以左右横跳的桌子？

第二个样例显然就是最坏情况的样例要n-1次领导夹菜我转桌吧

[Plumalis]

看样例2的话，难道每个人喜欢吃的还不唯一喽？

  

剧透

好久没写过代码了……已经忘光了，就随便写点伪代码大家看的懂就行

基础想法是计算每个菜离要吃的人的距离，只算一个方向，反正右转一个菜和左转n-1个菜是一样的不是嘛。

然后统计一下不同的距离一共多少，感觉应该就是正确解了？

readln(n);
for (i=1,i<=n,i++ ){
    read(j);
    a[i]= j - i;
    if (a[i]<0) a[i] = a[i]+n;
}

for  (i=1,i<=n,i++ ){
   if (a[i] != 0) b[a[i]]= 1;
}
integer answer = 0;
for (i=1,i<=n,i++ ){
    answer += b[i];
}

真的是……从高中以后就再也没搞过这个方面了，万一有错还请多包涵

 

四月 20, 2020，由wozaiha修改
补充思路？

[yhz012]

1 小时前, wozaiha 说道:

反正右转一个菜和左转n-1个菜是一样的不是嘛。

我傻了，我一直在算怎么最小化距离，忘了实际上距离不影响了