Форум » Массивы, сортировка, работа с файлами » задача 26-66 » Ответить

задача 26-66

Serov Sergej: Пытался решить задачу 26-66 "сканирующей прямой" на СИ++ с помощью структуры map. Но количество отрезков получается не 10358, а почему-то 10416. [pre2] #include <iostream> #include <map> #include <fstream> struct ser{//structura budet hranit' L (esli nachalo otrezka) R (esli konec) char lit; int count;// kolichestvo otrezkov s odinakovoj granicej }; using namespace std; int main(){ ifstream cin; cin.open("26-66.txt"); map <long long int, ser> m; long long int n,k,i,x,y,ma=100000000000,mi=0,kol=0; cin>>n>>k; for (i=0;i<n;i++){ cin>>x>>y; if (y==0)//v sluchae y=0 pravuju granicu delaem "daleko" vpravo y=ma; m[x].lit='L'; m[x].count=m[x].count+1; m[y].lit='R'; m[y].count=m[y].count+1; } for (auto w:m){//realizuem algoritm skaniruju prjamoj if (w.second.lit=='L'){ kol=kol+w.second.count; if (w.first>=k && kol>mi) mi=kol; } else kol=kol-w.second.count; } cout<<mi<<endl;//otvet pochemu-to 10416 vmesto 10358 } // hotja dlja primera v uslovii otvet daet pravil'nyj [/pre2]

Ответов - 3

Serov Sergej: Еще один непонятный момент: написал практически такой же алгоритм на Питоне (этим языком владею очень плохо), ответ получился 10511 [pre2] f = open('26-66.txt') n,k=map(int, f.readline().split()) a=[] b=[] pred=1000000000000 for i in range(n): x,y=map(int,f.readline().split()) if x in b: j=b.index(x) a[j][1]=a[j][1]+1 else: b.append(x) a.append([x,1,'L']) if y==0: y=pred if y in b: j=b.index(y) a[j][1]=a[j][1]+1 else: b.append(y) a.append([y,1,'R']) a.sort(key = lambda z: z[0]) nn=len(a) kol=0 mm=0 for i in range(nn): if a[i][2]=='L': kol=kol+a[i][1] if a[i][0]>=k and kol>mm: mm=kol else: kol=kol-a[i][1] print(mm) [/pre2]

Serov Sergej: На заключительном этапе сделал все команды ветвления независимыми, результат "улучшился" на 6: вместо 10416 стал 10410. [pre2] #include <iostream> #include <map> #include <fstream> struct ser{//structura budet hranit' L (esli nachalo otrezka) R (esli konec) char lit; int count;// kolichestvo otrezkov s odinakovoj granicej }; using namespace std; int main(){ ifstream cin; cin.open("26-66.txt"); map <long long int, ser> m; long long int n,k,i,x,y,ma=100000000000,mi=0,kol=0; cin>>n>>k; for (i=0;i<n;i++){ cin>>x>>y; if (y==0)//v sluchae y=0 pravuju granicu delaem "daleko" vpravo y=ma; m[x].lit='L'; m[x].count=m[x].count+1; m[y].lit='R'; m[y].count=m[y].count+1; } for (auto w:m){//realizuem algoritm skaniruju prjamoj if (w.second.lit=='R') kol=kol-w.second.count; if (w.first>=k && kol>mi) mi=kol; if (w.second.lit=='L') kol=kol+w.second.count; } cout<<mi<<endl;//otvet pochemu-to 10410 vmesto 10358 } // hotja dlja primera v uslovii otvet daet pravil'nyj [/pre2]

Поляков: На сайте есть авторские решения всех 26-х задач, сравнивайте с ними.




полная версия страницы