SRM696D2Med Arrfix
Div2Medにしては難しい
問題概要(原文)
数列 $A,B,F$ が与えられる．
全ての $i(1 \leq i \leq |F|)$ において， $A_{P_i} = F_i$ とする．という処理をする． このとき $P$ はdistinctでないといけない．
最終的に $A_i \neq B_i$ であるような $i$ の数を最小にしたい．
考察
- 貼って一致させられるやつは貪欲に貼る
- 貼って一致させられないやつは適当に損しないように貼る
- 余ったやつで，損しないやつから貪欲に貼る
- 残りの余ったやつは適当に貼る
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class Arrfix
{
public int mindiff(int[] A, int[] B, int[] F)
{
Debug.WriteLine(string.Join(" ", A));
Debug.WriteLine(string.Join(" ", B));
Debug.WriteLine(string.Join(" ", F));
var n = A.Length;
var gomi = 0;
var used = new bool[n];
for (int i = 0; i < F.Length; i++)
{
var p = -1;
for (int j = 0; j < n; j++)
{
if (used[j]) continue;
if (F[i] == B[j])
{
p = j;
if (B[j] != A[j])
{
A[j] = F[i];
break;
}
}
}
if (p == -1) gomi++;
else
{
used[p] = true;
}
}
var ans = 0;
for (int i = 0; i < n; i++)
{
if (A[i] == B[i]) ans++;
else if (!used[i]) gomi = Math.Max(0, gomi - 1);
}
return n - (ans - gomi);
}
}
コメント
- 落ち着いて考察したら簡単系
