Letöltés: kb_stafeta.cs using System; using System.Collections.Generic; using System.Text; using System.IO; namespace stafeta { // x alapján növekvőbe rendezi, ha x egyenlő, akkor y alapján csökkenőbe, hisze az a jó, ha tovább fut! class ascByStart : IComparer<Segment> { public int Compare(Segment a, Segment b) { if (a.x < b.x) return -1; else if (a.x > b.x) return 1; else { if (a.y > b.y) return -1; else if (a.y < b.y) return 1; else return 0; } } } // y alapján csökkenőbe rendezi, ha y egyenlő, akkor x alapján növekvő, hiszen ekkor az a jó ha hamar veszi át! class descByEnd : IComparer<Segment> { public int Compare(Segment a, Segment b) { if (a.y > b.y) return -1; else if (a.y < b.y) return 1; else { if (a.x < b.x) return -1; else if (a.x > b.x) return 1; else return 0; } } } class Segment { public int x, y, id; public Segment( int _x, int _y, int _id ) { x = _x; y = _y; id = _id; } public Segment Copy() { return new Segment( x, y, id ); } } class stafeta { private List<Segment> list; private List<Segment> list2; private List<int> ids; private int n, k; public stafeta() { StreamReader ins = new StreamReader("stafeta.be"); string[] line = ins.ReadLine().Split(' '); n = int.Parse(line[0]); k = int.Parse(line[1]); int id = 1; list = new List<Segment>(k); ids = new List<int>(k); for (int i = 0; i < k; i++) { line = ins.ReadLine().Split(' '); list.Add( new Segment( int.Parse(line[0]), int.Parse(line[1]), id++ ) ); } bool hiba = false; // kezdés szerint rendezünk list.Sort( new ascByStart() ); ids.Add( list[0].id ); // első tutira rendbe van -> ő kezdi! int last_idx = 0; int idx = 0; descByEnd sortDescByEnd = new descByEnd(); Segment tmp; while (true) { list2 = new List<Segment>(); idx = last_idx; // list[idx] futótól kell átvenni a lángot. // az adott indextől kezdve nézzük a futókat, addig ameddig ő még átveheti a lángot // őket a list2-ben tároljuk. do { idx++; if (idx == list.Count) break; if (list[last_idx].x <= list[idx].x && list[idx].x <= list[last_idx].y) { tmp = list[idx].Copy(); tmp.id = idx; // itteni ID tartalmazza a listben-i id-t! list2.Add(tmp); } else break; } while (true); // ezt a list2-t rendezzük befejezés szerint csökkenőbe -> az a legjobb aki legtovább futja. list2.Sort( sortDescByEnd ); last_idx = list2[0].id; // megjegyezzük az id-ját a list-ben. ids.Add(list[last_idx].id); // hozzáadjuk a sorszámát a megoldáshoz. // ha az adott futó lefutja a távolságot akkor vége. if (list[last_idx].y == n) break; } printOut( hiba ); } private void printOut( bool hiba ) { StreamWriter outs = new StreamWriter("stafeta.ki"); outs.WriteLine(ids.Count); for (int i = 0; i < ids.Count; i++) { outs.Write(ids[i] + " "); } outs.WriteLine(); outs.Close(); } static void Main(string[] args) { new stafeta(); } } } |