#java #алгоритм
Записался на курс алгоритмы и структуры данных. Не могу никак решить задачу: На числовой
прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка
(Li и Ri). Найти сумму длин частей числовой прямой, окрашенных ровно в один слой. Используемый
язык java, другие также принимаются
input
3
1 4
7 8
2 5
output 3
input
9
2 9
0 1
7 12
5 12
9 13
9 14
10 18
17 18
2 10
output
4
UPD
Что я пытался делать
1) сортировать все точки и держать к какому концу отрезка она находиться
на 1 первый тест легко пишутся условия когда нужно посчитать сумму ко 2му не подходит
int sum = 0;
if(mass.length==1) sum+=mass[1].dot-mass[0].dot;
else { sum+= mass[1].dot-mass[0].dot;
for (int i = 2; i < n * 2; i++) {
if(mass[i].l==false){ // если это не левый конец
if (mass[i-1].l==false) sum+=mass[i].dot-mass[i-1].dot;
if(mass[i-1].l==true&&mass[i-2].l==false) sum+=mass[i].dot-mass[i-1].dot;
}else {
if(mass[i-1].l==true) sum+= mass[i].dot-mass[i-1].dot;
}
2) Сортировать все отрезки в виде классов (point( 1 4) point (2 5) point (7 8))
также с ифами все возможные варианты не получилось покрыть,
Есть какие-то еще идеи или только в этих 2-х направлениях нужно искать подходящие
условия срабатывания счетчика
UPD
Вот похожая задача на нахождение длины объединения отрезков на прямой.
ток не совсем понимаю синтаксис и как перевести на java
unsigned segments_union_measure (const vector > & a)
{
unsigned n = a.size();
vector > x (n*2);
for (unsigned i=0; i
Ответы
Ответ 1
Задачи на интервалы решаются сортировкой координат, и перебором подряд от меньших
к большим, считая «текущее» кол-во активных.
Напр., даны отрезки [1,5], [2,3], [3,9]
Тут ещё важно, каковы крайние точки - для простоты считаем, что все края «включены».
Сортируем координаты, не забывая, где какая - одни из них точки входа (in), другие
- выхода (out):
1 i
2 i
3 o
3 i
5 o
9 o
Изначально кол-во включённых слоёв 0. Когда "i" добавляем 1, когда "o" – вычитаем. Пошли:
- - 0
1 i 1 - начался нужный отрезок - в результат добавим [1, ?
2 i 2 - != 1, закончился – в результат добавили [1,2]
3 o 1 - снова начался нужный
3 i 2 - и тут же закончился, ничего не делаем
5 o 1 - начался нужный [5, ?
9 o 0 - закончился, в результат добавили [5,9]
Результат: [1,2], [5,9]. Складываем длины 1+4 = 5. Ответ: 5
Ответ 2
В условии задачи было сказано: "ровно в один слой", и идеи с объединением отрезков
здесь не проходят.
Но можно воспользоваться методом интервалов, для чего:
1. Свалить все начала и концы отрезков в один массив и упорядочить.
2. На каждом из полученных отрезков ненулевой длины выбрать внутреннюю точку (например,
середину) и подсчитать, скольким исходным отрезкам она принадлежит.
3 Просуммировать длины отрезков, для которых сумма по п.3 равна 1.
Программа на PHP:
$segments = [
[2,9],
[0,1],
[7,12],
[5,12],
[9,13],
[9,14],
[10,18],
[17,18],
[2,10]
];
var_dump($segments);
$begend=[];
foreach ($segments as $seg) array_push($begend, $seg[0], $seg[1]);
sort($begend);
var_dump($begend);
$cnt = count($begend);
$begin = $begend[0];
$length = 0;
for($i=1; $i < $cnt; $i++){ // проверяем каждый интервал, образованный краями отрезков
$end = $begend[$i];
if($end!=$begin){
$c = 0;
$aver = ($begin+$end)/2;
foreach($segments as $seg){
if ($seg[0]<$aver && $aver < $seg[1]) $c++;
}
if($c==1) $length += ($end - $begin);
print("
начало: $begin конец: $end повторов: $c сумма = $length");
$begin = $end;
}
}
print("
length = $length");
Результаты:
array (size=9)
0 =>
array (size=2)
0 => int 2
1 => int 9
1 =>
array (size=2)
0 => int 0
1 => int 1
2 =>
array (size=2)
0 => int 7
1 => int 12
3 =>
array (size=2)
0 => int 5
1 => int 12
4 =>
array (size=2)
0 => int 9
1 => int 13
5 =>
array (size=2)
0 => int 9
1 => int 14
6 =>
array (size=2)
0 => int 10
1 => int 18
7 =>
array (size=2)
0 => int 17
1 => int 18
8 =>
array (size=2)
0 => int 2
1 => int 10
array (size=18)
0 => int 0
1 => int 1
2 => int 2
3 => int 2
4 => int 5
5 => int 7
6 => int 9
7 => int 9
8 => int 9
9 => int 10
10 => int 10
11 => int 12
12 => int 12
13 => int 13
14 => int 14
15 => int 17
16 => int 18
17 => int 18
начало: 0 конец: 1 повторов: 1 сумма = 1
начало: 1 конец: 2 повторов: 0 сумма = 1
начало: 2 конец: 5 повторов: 2 сумма = 1
начало: 5 конец: 7 повторов: 3 сумма = 1
начало: 7 конец: 9 повторов: 4 сумма = 1
начало: 9 конец: 10 повторов: 5 сумма = 1
начало: 10 конец: 12 повторов: 5 сумма = 1
начало: 12 конец: 13 повторов: 3 сумма = 1
начало: 13 конец: 14 повторов: 2 сумма = 1
начало: 14 конец: 17 повторов: 1 сумма = 4
начало: 17 конец: 18 повторов: 2 сумма = 4
length = 4
Ответ 3
Шлифуем алгоритм (с учётом замечания Sergics):
Создаём массив начал и концов по отрезкам.
Создаём массив знаков: +1 для начала отрезка и -1 - для конца.
Сортируем оба массива по координате (процедура array_multisort()).
Количество слоёв получаем суммированием массива знаков.
Программа (PHP):
$segments = [
[2,9],
[0,1],
[7,12],
[5,12],
[9,13],
[9,14],
[10,18],
[17,18],
[2,10]
];
var_dump($segments);
$begend=[];
$sign = [];
foreach ($segments as $seg){
array_push($begend, $seg[0], $seg[1]);
array_push($sign, 1, -1);
}
array_multisort($begend, $sign);
$size = count($begend);
$length = 0;
$c = $sign[0];
$begin = $begend[0];
for ($i = 1; $i < $size; $i++){
if($c == 1) $length += $begend[$i] - $begin;
printf("
Интервал: [%2d,%2d] Знак: %s Слоёв: $c Сумма:
$length",
$begin, $begend[$i], ($sign[$i-1]>0)?"+":"-");
$c += $sign[$i];
$begin = $begend[$i];
}
print("
length = $length");
Результаты:
array (size=9)
0 =>
array (size=2)
0 => int 2
1 => int 9
1 =>
array (size=2)
0 => int 0
1 => int 1
2 =>
array (size=2)
0 => int 7
1 => int 12
3 =>
array (size=2)
0 => int 5
1 => int 12
4 =>
array (size=2)
0 => int 9
1 => int 13
5 =>
array (size=2)
0 => int 9
1 => int 14
6 =>
array (size=2)
0 => int 10
1 => int 18
7 =>
array (size=2)
0 => int 17
1 => int 18
8 =>
array (size=2)
0 => int 2
1 => int 10
Интервал: [ 0, 1] Знак: + Слоёв: 1 Сумма: 1
Интервал: [ 1, 2] Знак: - Слоёв: 0 Сумма: 1
Интервал: [ 2, 2] Знак: + Слоёв: 1 Сумма: 1
Интервал: [ 2, 5] Знак: + Слоёв: 2 Сумма: 1
Интервал: [ 5, 7] Знак: + Слоёв: 3 Сумма: 1
Интервал: [ 7, 9] Знак: + Слоёв: 4 Сумма: 1
Интервал: [ 9, 9] Знак: + Слоёв: 5 Сумма: 1
Интервал: [ 9, 9] Знак: + Слоёв: 6 Сумма: 1
Интервал: [ 9,10] Знак: - Слоёв: 5 Сумма: 1
Интервал: [10,10] Знак: - Слоёв: 4 Сумма: 1
Интервал: [10,12] Знак: + Слоёв: 5 Сумма: 1
Интервал: [12,12] Знак: - Слоёв: 4 Сумма: 1
Интервал: [12,13] Знак: - Слоёв: 3 Сумма: 1
Интервал: [13,14] Знак: - Слоёв: 2 Сумма: 1
Интервал: [14,17] Знак: - Слоёв: 1 Сумма: 4
Интервал: [17,18] Знак: + Слоёв: 2 Сумма: 4
Интервал: [18,18] Знак: - Слоёв: 1 Сумма: 4
length = 4
Ответ 4
Мне кажется самым простым решением, создать массив длиной N, где N - длина числовой
прямой. Массив заполнен нулями. Далее нанести отрезки на массив, увеличивая на 1 каждый
фрагмент(отрезок) массива. Последним этапом пройти по массиву и подсчитать количество 1.
Для первого примера:
[0,0,0,0,0,0,0] // размерность - 7
[1,1,1,0,0,0,0] // [1,4]
[1,1,1,0,0,0,1] // [7,8]
[1,2,2,1,0,0,1] // [2,5]
Ответ 5
Вот программа на java кот может решить вашу задачу
import java.io.IOException;
import java.util.Comparator;
public class Main {
public static void main(String[] args) throws IOException {
Point[] points = new Point[nextInt()<<1];
for (int i = 0; i < points.length; i++) {
points[i] = new Point(nextInt(), 1);
points[++i] = new Point(nextInt(), -1);
}
mergeSortIterative(points, 0, points.length, (p1, p2) -> {
int val = p1.getP() - p2.getP();
return val == 0 ? -p1.getV() : val;
});
int res = countLen( points );
System.out.println(res);
}
public static int countLen( Point[] arr ){
int res = 0;
int count = arr[0].getV();
Point prev = arr[0];
for (int i = 1; i < arr.length; i++) {
count += arr[i].getV();
arr[i].setV(count);
if ( prev.getV() == 1 && prev.getP() != arr[i].getP() )
res += arr[i].getP() - prev.getP();
prev = arr[i];
}
return res;
}
public static void mergeSortIterative(T[] arr, int l, int
r, Comparator comp) {
if (l + 1 < r) {
int m = ( l + r ) >>> 1;
mergeSortIterative(arr, l, m, comp);
mergeSortIterative(arr, m, r, comp);
int len = r - l;
T[] tmp = (T[]) new Object[len];
for (int i = 0, j1 = l, j2 = m ; i < len; i++) {
if ( j2 >= r || j1 < m && comp.compare(arr[j1], arr[j2]) < 0 )
tmp[i] = arr[j1++];
else
tmp[i] = arr[j2++];
}
System.arraycopy(tmp, 0 , arr, l, len);
}
}
private static int nextInt() throws IOException {
int d;
int val = 0;
while ((d = System.in.read()) == 32) ;
if (d < 0) return Integer.MIN_VALUE;
boolean flag = false;
if (d == '-') {
flag = true;
d = System.in.read();
}
do {
val += d - 48;
if ((d = System.in.read()) < 48 || d > 57) break;
val *= 10;
} while (true);
return flag ? -val : val;
}
private static class Point{
private int p;
private int v;
public Point(int p, int v){
this.p = p;
this.v = v;
}
public int getP() {
return p;
}
public int getV() {
return v;
}
public void setV(int v) {
this.v = v;
}
public void setP(int p) {
this.p = p;
}
@Override
public String toString() {
return getP()+"("+getV()+") ";
}
}
}
Комментариев нет:
Отправить комментарий