7218 | 2024. 01. 03 18:28:07 | czita | A lehető legkevesebb átszállás (50 pont) | csharp | Elfogadva 50/50 | 50ms | 31192 KiB |
using System;
using System.Collections.Generic;
namespace átszállás
{
internal class Program
{
static int[] be()
{
string[] sts = Console.ReadLine().Split(' ');
int[] st = new int[3];
st[1] = int.Parse(sts[1]);
st[0] = int.Parse(sts[0]);
return st;
}
static void Main(string[] args)
{
int[] st = be();//alapadatok beolvasása
int N = st[1];
int M = st[0];
st = be();//első vonat beolvasása
List<int[]> v = new List<int[]>();
st[2] = 1;
if (st[0] != 1) Console.WriteLine(-1);//nem a kezdőállomásról indulaz elős vonat
else
{
int indulas = st[0], erkezes = st[1], vonat = 1;
for (int i = 1; i <= M; i++)
{
if (indulas == st[0])
{
if (erkezes < st[1])
{
erkezes = st[1];//az adott állomásról a legtávolabb menő vonat
vonat = i;
}
}
else
{
int[] t = new int[3];
t[0] = indulas;
t[1] = erkezes;
t[2] = vonat;
v.Add(t);
indulas = st[0];
erkezes = st[1];
vonat = i;
}
if (i < M) st = be();
}
int[] t1 = new int[3];
t1[0] = indulas;
t1[1] = erkezes;
t1[2] = vonat;
v.Add(t1);
//belső intervallumok kizárása
List<int[]> v2 = new List<int[]>();
v2.Add(v[0]);
erkezes = v[0][1];
foreach (var item in v)
{
if (item[1] > erkezes)
{
v2.Add(item);
erkezes = item[1];
}
}
//a legkedvezőbb intevallumok kiváasztása
List<int[]> v3 = new List<int[]>();
if (v2.Count == 1)
{
v3.Add(v2[0]);
}
else
{
v3.Add(v2[0]);
erkezes = v2[0][1];
int maxi = 1;
for (int i = 1; i < v2.Count; i++)
{
if (v2[i][0] <= erkezes)
{
if (v2[i][1] > v2[maxi][1])
{
maxi = i;
}
}
else
{
v3.Add(v2[maxi]);
erkezes = v2[maxi][1];
maxi = i;
}
}
v3.Add(v2[maxi]);
}
//van e átfedés
int cv = 1;
while (cv < v3.Count && v3[cv][0] <= v3[cv - 1][1])
{
cv++;
}
if (cv < v3.Count||v3[v3.Count-1][1]!=N)
{
Console.WriteLine(-1);
}
else
{
Console.WriteLine(v3.Count - 1);
foreach (var item in v3)
{
Console.Write(item[2] + " ");
}
Console.WriteLine();
}
}
Console.ReadKey();
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 30ms | 20944 KiB | |||
2 | Elfogadva | 0/0 | 46ms | 28192 KiB | |||
3 | Elfogadva | 1/1 | 28ms | 21948 KiB | |||
4 | Elfogadva | 1/1 | 28ms | 21964 KiB | |||
5 | Elfogadva | 2/2 | 28ms | 22432 KiB | |||
6 | Elfogadva | 2/2 | 28ms | 22556 KiB | |||
7 | Elfogadva | 2/2 | 32ms | 23480 KiB | |||
8 | Elfogadva | 2/2 | 32ms | 23920 KiB | |||
9 | Elfogadva | 2/2 | 34ms | 24556 KiB | |||
10 | Elfogadva | 2/2 | 35ms | 25408 KiB | |||
11 | Elfogadva | 2/2 | 37ms | 26080 KiB | |||
12 | Elfogadva | 2/2 | 39ms | 26780 KiB | |||
13 | Elfogadva | 2/2 | 32ms | 24172 KiB | |||
14 | Elfogadva | 2/2 | 35ms | 24748 KiB | |||
15 | Elfogadva | 2/2 | 35ms | 25432 KiB | |||
16 | Elfogadva | 2/2 | 39ms | 27084 KiB | |||
17 | Elfogadva | 2/2 | 43ms | 28380 KiB | |||
18 | Elfogadva | 2/2 | 45ms | 29216 KiB | |||
19 | Elfogadva | 2/2 | 48ms | 29872 KiB | |||
20 | Elfogadva | 2/2 | 48ms | 29964 KiB | |||
21 | Elfogadva | 2/2 | 48ms | 30836 KiB | |||
22 | Elfogadva | 2/2 | 48ms | 30768 KiB | |||
23 | Elfogadva | 2/2 | 48ms | 30800 KiB | |||
24 | Elfogadva | 2/2 | 48ms | 30532 KiB | |||
25 | Elfogadva | 2/2 | 48ms | 31172 KiB | |||
26 | Elfogadva | 2/2 | 48ms | 31192 KiB | |||
27 | Elfogadva | 2/2 | 48ms | 31068 KiB | |||
28 | Elfogadva | 2/2 | 50ms | 31148 KiB |