Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 26.06.2015, 23:17   #1
Тамерлан Абилов
Пользователь
 
Регистрация: 03.03.2013
Сообщений: 70
Радость Новогодние подарки.Жадный алгоритм.

Добрый вечер.

Люди помогите понять, как тут применить жадность.

Все что в голову пришло не подходить весь день думал.Только знаю что должно получиться максимальное пересечение между временем отправки и упаковкой другого подарка,та последовательность будет и оптимальней.но как это использовать не знаю..думал все что можно .Сортировать по максимальным пересечением не вариант..просто увеличению времени приготовления подарка не робит. Просто подскажите отсталому что тут применять ,буду счастлив

Деду Морозу и Снегурочке нужно доставить n подарков детям.

Зная время t1 упаковки каждого подарка Снегурочкой и время его доставки Дедом Морозом t2, вычислить наименьшее время, необходимое для выполнения всех заказов. В свой мешок Дед Мороз может положить только один подарок.

Входные данные

В первой строке находится количество подарков n (1 ≤ n ≤ 300). В следующих двух строках содержится по n чисел, соответственно: во второй строке – время упаковки каждого подарка Снегурочкой, а в третьей – время его доставки Дедом Морозом. Известно, что 0 < t1, t2 ≤ 1000.

Выходные данные

Наименьшее время доставки всех подарков.

Входные данные

5
4 4 30 6 2
5 1 4 30 3


Выходные данные

47
Тамерлан Абилов вне форума Ответить с цитированием
Старый 27.06.2015, 11:30   #2
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Называется это чудо - алгоритм Джонсона
Вечером скину свой вариант
Poma][a вне форума Ответить с цитированием
Старый 28.06.2015, 12:15   #3
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Код:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <list>

using namespace std;

bool f(const pair<int, int>& a, const pair<int, int>& b)
{
	return min(a.first, a.second) < min(b.first, b.second);
}

int main()
{
	int n;
	cin >> n;

	vector <pair<int, int> > v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i].first;
	
	for (int i = 0; i < n; i++)
		cin >> v[i].second;
	
	sort(v.begin(), v.end(), f);

	list < pair<int, int> > first, second;

	for (int i = 0; i < n; i++)
		if (v[i].first < v[i].second)
			first.push_back(v[i]);
		else
			second.push_front(v[i]);

	first.splice(first.end(), second);
	
	int a = 0, b = 0;
	
	for (list < pair<int, int> >::iterator p = first.begin(); p != first.end(); ++p)
	{
		a += p->first;
		b = max(b, a) + p->second;
	}

	cout << b;
	return 0;
}
Вечер чуть затянулся
Poma][a вне форума Ответить с цитированием
Старый 02.07.2015, 16:51   #4
Тамерлан Абилов
Пользователь
 
Регистрация: 03.03.2013
Сообщений: 70
По умолчанию

Спасибо!)Очень помог
Конечно я не понял откуда он смотрит на компоратор...и делает доводы по поводу если А - то раньше.если Б то позже.

А так, смотря на компоратор явно видем что добиваемся максимального пересечение - что радует
Код:
import java.util.Scanner;
import java.util.Arrays;
public class Djons2{
	
	public static void main(String[] aaa){

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] pr = new int[n][2];
		for ( int i = 0; i < n * 2; i++){

			pr[i%n][i/n] = sc.nextInt();
		
		}

		Arrays.sort(pr,(int[] p1, int[] p2) -> Math.min(p1[0], p2[1]) - Math.min(p2[0], p1[1]));
		int result = 0, a = 0 ;
		for (int[] p:pr){

			a += p[0];
			result = Math.max(result, a) + p[1]; 

		}
		System.out.println(result);

	}




}
Тамерлан Абилов вне форума Ответить с цитированием
Старый 03.07.2015, 22:54   #5
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Конечно я не понял откуда он смотрит на компоратор
Всмысле? Почему он именно такой?
Poma][a вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Жадный алгоритм на графе slimper86 Помощь студентам 4 27.06.2013 09:31
Разыгрываем и дарим Новогодние подарки от форума :) Alar Свободное общение 42 31.12.2012 17:16
Жадный алгоритм? Loki_veil Помощь студентам 0 27.06.2012 12:05
Жадный алгоритм merhaba1992 Помощь студентам 1 05.11.2011 00:24
Жадный алгоритм в программировании nikita92 Помощь студентам 0 26.11.2010 20:20