AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC217-D Cutting Woods
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5 3");
WillReturn.Add("2 2");
WillReturn.Add("1 3");
WillReturn.Add("2 2");
//5
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("5 3");
WillReturn.Add("1 2");
WillReturn.Add("1 4");
WillReturn.Add("2 3");
//2
}
else if (InputPattern == "Input3") {
WillReturn.Add("100 10");
WillReturn.Add("1 31");
WillReturn.Add("2 41");
WillReturn.Add("1 59");
WillReturn.Add("2 26");
WillReturn.Add("1 53");
WillReturn.Add("2 58");
WillReturn.Add("1 97");
WillReturn.Add("2 93");
WillReturn.Add("1 23");
WillReturn.Add("2 84");
//69
//31
//6
//38
//38
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int L = wkArr[0];
var BundanDict = new SortedList<int, bool>();
// 番兵をAdd
BundanDict[0] = false;
BundanDict[L] = false;
var sb = new System.Text.StringBuilder();
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
if (wkArr[0] == 1) {
BundanDict.Add(wkArr[1], false);
}
if (wkArr[0] == 2) {
int ResultInd = ExceNibunhou(BundanDict, wkArr[1]);
int CurrKey = BundanDict.Keys[ResultInd];
int PrevKey = BundanDict.Keys[ResultInd - 1];
int Length = CurrKey - PrevKey;
sb.AppendLine(Length.ToString());
}
}
Console.Write(sb.ToString());
}
// 二分法で、引数以上の最小値の、キーの配列の添字を返す
static int ExceNibunhou(SortedList<int, bool> pSortedList, int pTargetVal)
{
int UB = pSortedList.Count - 1;
var Keys = pSortedList.Keys;
int L = 0;
int R = UB;
while (L + 1 < R) {
int Mid = (L + R) / 2;
if (Keys[Mid] < pTargetVal) {
L = Mid;
}
else {
R = Mid;
}
}
return R;
}
}
解説
平衡二分木であるSortedListで
切った場所を管理して
木の長さの問い合わせが来たら、
二分法で前後の切った位置を求めてます。