W ramach nauki c# rozwiązuje zadanie: treść zadania., ale pomimo otrzymania prawidłowego rozwiązania dla danych przykładowych próba zaliczenia kończy się komunikatem "błąd wykonania (NZEC)".
Mój pomysł na algorytm:
- podzielić wczytane dane na dwa zestawy
- A - znajomi, którzy nie wpłacą bez konieczności ich przekonywania .
- B - znajomi, którzy wpłacą jeżeli jest odpowiedni poziom Di.
- wstępnie wyznaczyć ilu znajomych mniej więcej trzeba przekonać, sprawdzając:
- czy cel jest osiągalny bez przekonywania,
- czy minDi (minimalny poziom z całego zestawu) zostanie osiągnięty i kolejny znajomy wpłaci.
- Na podstawie tej wstępnej liczby znajomych do przekonania:
- sprawdzić ich i-ty indeks (z wczytanego zestawu) w zestawie A.
- wyszukać binarnie następny i-ty indeks (z wczytanego zestawu) przeszukując tylko zestaw B.
- w pętli sprawdzać kolejnych znajomych z zestawu B od wyszukanego indeksu do końca i sumować cel
Pewnie będzie to mało jasne więc załączam poniżej kod. Zaznaczam, że jestem świeżakiem więc liczę na wyrozumiałość w stosunku do kodu jak i nazw zmiennych/metod.
Proszę o wsparcie w znalezieniu błędu. Chętnie też dowiem się czy da się to napisać optymalniej od strony algorytmu jak i składni.
using System;
using System.Collections.Generic;
class Friend
{
private readonly int indexInSet;
private int di;
public int Iset { get => indexInSet; }
public int Di { get => di; set => di = value; }
public Friend(int i)
{
this.indexInSet = i;
}
public Friend(int i, int Di)
{
this.indexInSet = i;
this.Di = Di;
}
}
class Program
{
static int goal;
static int friends;
static List<Friend> toConvinceList;
static List<Friend> conditionFriendsList;
static int minDi;
private static void ReadSet()
{
string[] friendsAndGoal = Console.ReadLine().Split(' ');
friends = int.Parse(friendsAndGoal[0]);
goal = int.Parse(friendsAndGoal[1]);
string[] zestawString = Console.ReadLine().Split(' ');
int[] set = Array.ConvertAll(zestawString, int.Parse);
minDi = Int32.MaxValue;
toConvinceList = new List<Friend>();
conditionFriendsList = new List<Friend>();
SeperateSetToLists(ref set);
Console.WriteLine(CountHowManyMustBeConvinced(ref toConvinceList, ref conditionFriendsList));
}
private static void SeperateSetToLists(ref int[] set)
{
for (int i = 0; i < friends; i++)
{
if (set[i] >= i + 1)
{ //Di zbyt wysokie aby wplacili bez przekonywania
toConvinceList.Add(new Friend(i));
}
else
{ //warunkowo moga wplacic
conditionFriendsList.Add(new Friend(i, set[i]));
if (set[i] < minDi)
{
minDi = set[i];
}
}
}
if (minDi == Int32.MaxValue)
{
minDi = 0;
}
}
private static int CountHowManyMustBeConvinced(ref List<Friend> toConvinceList, ref List<Friend> conditionFriendsList)
{
int conditionFriendsCounted = conditionFriendsList.Count;
int convince;
//ilu wstepnie nalezy przekonac sprawdzajac ilu znajomych jest skora wplacic
if ((goal - conditionFriendsCounted) > 0)
{
convince = goal - conditionFriendsCounted;
if (convince == goal)
{
return goal;
}
}
else
convince = 0;
//jakie jest najmniejsze Di w stosunku do tego ilu chcemy przekonac
if (minDi > convince)
{
if (goal <= minDi)
{
return goal; //minimalne Di jest za duze, aby znajomi zaczeli wplacac oraz cel jest osiagalny samym wstepnym przekonaniem.
}
else
{
convince = minDi;
}
}
//liczenie przekonanych;
int toConvinceListCounted = toConvinceList.Count;
int beginIndex = 0;
int sum = 0;
if (convince > 0)
{
beginIndex = SearchIndexWithNearestGreaterValue(toConvinceList[convince - 1].Iset, ref conditionFriendsList);
sum = toConvinceList[convince - 1].Iset + 1;
}
do
{
for (int i = beginIndex; i < conditionFriendsCounted; i++)
{
if (sum >= conditionFriendsList[i].Di) {sum++;}
}
if (GoalAchieved(goal, sum)){return convince;}
beginIndex = SearchIndexWithNearestGreaterValue(toConvinceList[++convince - 1].Iset, ref conditionFriendsList);
sum = toConvinceList[convince - 1].Iset + 1;
} while (true);
}
private static int SearchIndexWithNearestGreaterValue(int index, ref List<Friend> list)
{
int min = 0;
int max = list.Count - 1;
int mid = max / 2;
int loopCountTarget = ((int)Math.Round(Math.Log(Convert.ToDouble(max), 2), 0)) + 1;
int result = max + 1;
for (; loopCountTarget > 0; loopCountTarget--)
{
if (list[mid].Iset > index)
{
result = mid;
max = mid;
mid = (max - (max - min)) / 2;
}
else
{
min = mid;
mid = min + (max - min) / 2;
}
}
return result;
}
private static bool GoalAchieved(int goal, int sum)
{
return goal <= sum ? true : false;
}
static void Main()
{
int countedSets = int.Parse(Console.ReadLine());
while (countedSets-- > 0)
{
ReadSet();
}
//Console.ReadLine(); //break
}
}