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);
    }
}

コメント

  • 落ち着いて考察したら簡単系