B. Two Cakestime limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Sasha and Dima want to buy two nn -tier cakes. Each cake should consist of nn different tiers: from the size of 11 to the size of nn . Tiers should go in order from the smallest to the biggest (from top to bottom).
They live on the same street, there are 2⋅n2⋅n houses in a row from left to right. Each house has a pastry shop where you can buy a cake tier. Unfortunately, in each pastry shop you can buy only one tier of only one specific size: in the ii -th house you can buy a tier of the size aiai (1≤ai≤n1≤ai≤n ).
Since the guys carry already purchased tiers, and it is impossible to insert a new tier in the middle of the cake, they agreed to buy tiers from the smallest to the biggest. That is, each of them buys tiers in order: 11 , then 22 , then 33 and so on up to nn .
Initially, Sasha and Dima are located near the first (leftmost) house. Output the minimum distance that they will have to walk in total to buy both cakes. The distance between any two neighboring houses is exactly 11 .
Input
The first line of the input contains an integer number nn — the number of tiers in each cake (1≤n≤1051≤n≤105 ).
The second line contains 2⋅n2⋅n integers a1,a2,…,a2na1,a2,…,a2n (1≤ai≤n1≤ai≤n ), where aiai is equal to the size of the tier, which can be bought in the ii -th house. Remember that in each house you can buy only one tier. It is guaranteed that every number from 11 to nn occurs in aa exactly two times.
Output
Print one number — the minimum distance that the guys have to walk in total to buy both cakes. Guys can be near same house at the same time. They begin near the first (leftmost) house. Each of the guys should buy nn tiers in ascending order of their sizes.
ExamplesInput
Copy
3
1 1 2 2 3 3
Output
Copy
9
Input
Copy
2
2 1 1 2
Output
Copy
5
Input
Copy
4
4 1 3 2 2 3 1 4
Output
Copy
17
Note
In the first example, the possible optimal sequence of actions is:
- Sasha buys a tier of size 11 near the 11 -st house (a1=1a1=1 );
- Dima goes to the house 22 ;
- Dima buys a tier of size 11 near the 22 -nd house (a2=1a2=1 );
- Sasha goes to the house 44 ;
- Sasha buys a tier of size 22 near the 44 -th house (a4=2a4=2 );
- Sasha goes to the house 55 ;
- Sasha buys a tier of size 33 near the 55 -th house (a5=3a5=3 );
- Dima goes to the house 33 ;
- Dima buys a tier of size 22 near the 33 -rd house (a3=2a3=2 );
- Dima goes to the house 66 ;
- Dima buys a tier of size 33 near the 66 -th house (a6=3a6=3 ).
So, Sasha goes the distance 3+1=43+1=4 , and Dima goes the distance 1+1+3=51+1+3=5 . In total, they cover a distance of 4+5=94+5=9 . You can make sure that with any other sequence of actions they will walk no less distance.
这是一个贪心题目，隐隐约约意识到了，但是我贪心并没有学好，所以自己没有写对，然后看了别人的代码，觉得写的真好。
这个我之前认为每一个数字的处理，会有后效性，也就是会对后面的结果产生影响，所以就写的畏畏缩缩的，然后就错了，而且我很喜欢用结构体，所以就用结构体来储存所有的数，这个不太好。
然后就是要消去后效性，那就用贪心，对待每一层，从1开始贪心，具体看代码，这里其实没有后效性。
然后再贴另一个代码，我不知道为什么AC了的，别人写的。
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int l[maxn], r[maxn];
int a[maxn];int main()
{
int n;
cin >> n;
for(int i=1;i<=2*n;i++)
{
scanf("%d", &a[i]);
if (!l[a[i]]) l[a[i]] = i;
else r[a[i]] = i;
}
ll ans=l[1]-1+r[1]-1;
for(int i=1;i<n;i++)
{
ans += min(abs(l[i + 1] - l[i]) + abs(r[i + 1] - r[i]), abs(l[i + 1] - r[i]) + abs(l[i] - r[i + 1]));
}
printf("%I64d\n", ans);
return 0;
}
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
int l[maxn], r[maxn];
int a[maxn];int main()
{
int n;
cin >> n;
for(int i=1;i<=2*n;i++)
{
scanf("%d", &a[i]);
if (!l[a[i]]) l[a[i]] = i;
else r[a[i]] = i;
}
ll ans = 0;
int L = 1, R = 1;
for(int i=1;i<=n;i++)
{
ans += abs(l[i] - L);
ans += abs(r[i] - R);
L = l[i];
R = r[i];
}
printf("%I64d\n", ans);
return 0;
}
