Programozás‎ > ‎Feladatok‎ > ‎Staféta‎ > ‎Megoldás‎ > ‎

kb_stafeta.cs

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();
        }
    }
}