Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) B. Two Cakes(思维)

题目链接:http://codeforces.com/contest/1130/problem/B

       题意是输入一个n说明编号为1-n的蛋糕,然后输入2*n个数,表示编号为ai的蛋糕在第i个位置(1-n每个数出现两次),现在有两个人在第一个位置,他们两个人要分别要拿n个蛋糕,且只能按1-n的顺序拿蛋糕,每走一步的时间为1,问最少多长时间两个人能取完蛋糕。

       思路是因为每个数一定出现两次,而且两个人都是按1-n的顺序拿蛋糕,所以我们编号为i的蛋糕,我们对两个人进行一个比较,使两个人都拿到第i个蛋糕的所用时间最小就好了,因为只有两种情况(a1拿b1,a2拿b2 或者 a1拿b2,a2拿b1)。具体实现方法就是将蛋糕和它的位置存起来,枚举第i号蛋糕,比较两种情况的最小值,然后更新两个人的位置就好了。


AC代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
vector<int> v[100005];

int main()
{
  scanf("%d",&n);
  for(int i=1;i<=2*n;i++){
    int x;
    scanf("%d", &x);
    v[x].push_back(i);
  }
  int t1 = 1, t2 = 1;
  ll ans = 0;
  for(int i=1;i<=n;i++){
    int xx = abs(t1 - v[i][0]) + abs(t2 - v[i][1]);
    int yy = abs(t1 - v[i][1]) + abs(t2 - v[i][0]);
    ans += min(xx, yy);
    t1 = v[i][0];
    t2 = v[i][1];
    
  }
  printf("%lld\n", ans);
  return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券