Първо контролно за BOI 2004, Задача 3. НИЗОВЕ
Уловието на задачата може да прочетете тук.
Решение
Задачата
може да се реши по различни начини, с използване на различни структури и
подходи. Но възползвайки се от ограниченията на задачата може да приложим много
лесен подход, който включва едно сортиране и едно обхождане на низовете.
Първо
ще сортираме низовете лексикографски. След сортирането, еднаквите низове ще
стоят един след друг. После ще обходим сортираната последователност като броим еднаквите
низове и съответно ще запазим този, който се среща най-малко. Освен това за
всяка последователност от еднакви низове трябва да запазваме този с най-малък
номер в началната последователност. Това се прави с цел при равен брой срещания
на два низа да изберем този, който се среща по-рано.
Горе-описания
подход най-лесно ще се реализира ако направим един масив с числата от 1
до N, като всяко ще бъде индекс
в оригиналния масив с низове. Така сортирайки числата относно низовете, ще
имаме и поредните номера на всеки низ в началната последователност.
Примерна реализация
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 100000;
const int maxl = 12;
int n, ans;
int ix[maxn];
char s[maxn][maxl];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, cb, cc, cm;
void readf();
void writef();
int icmp(const void* i1, const void *i2);
readf();
for (i = 0; i < n; i++)
ix[i] = i;
qsort(ix, n, sizeof(int), icmp);
cb = maxn + 1;
cc = 1;
cm = ix[0];
for (i = 1; i < n; i++)
{
if (strcmp(s[ix[i]], s[ix[i-1]]) == 0)
{
cc++;
cm = min(cm, ix[i]);
}
else
{
if (cc < cb || cc == cb && cm < ans)
{
cb = cc;
ans = cm;
}
cc = 1;
cm = ix[i];
}
}
writef();
}
void readf()
{
int i;
cin >> n;
for (i = 0; i < n; i++)
cin >> s[i];
}
void writef()
{
cout << s[ans] << '\n';
}
int icmp(const void* i1, const void *i2)
{
int r, x1, x2;
x1 = *(int*)i1;
x2 = *(int*)i2;
r = strcmp(s[x1], s[x2]);
return ((r != 0) ? r : x1 - x2);
}
Автор: Иван Анев
обратно към брой 26
|