Шеф-повар Ада готовит N блюд (пронумерованных от 1 до N). Для каждого действительного i на приготовление i-го блюда уходит Ci минут. Блюда можно готовить в любом порядке.
У Ады есть кухня с двумя одинаковыми конфорками. На каждое действительное ii для приготовления i-го блюда она ставит его на одну из конфорок и через Ci минут снимает с этой конфорки; блюдо нельзя снимать с конфорки до истечения этих минут CiCi, иначе оно остынет и испортится. Любые два блюда могут быть приготовлены одновременно, однако никакие два блюда не могут находиться на одной и той же конфорке одновременно. Ада может снять тарелку с конфорки и одновременно поставить другую тарелку на ту же конфорку.
Какое минимальное время необходимо для приготовления всех блюд, т.е. до состояния, когда все блюда готовы?
Вход
- Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
- Первая строка каждого набора входных данных содержит одно целое число N.
- Во второй строке через пробел записаны N целых чисел C1, C2,…, CN.
Вывод
Для каждого набора входных данных выведите одну строку, содержащую одно целое число ― минимальное количество минут, необходимое для приготовления всех блюд.
Ограничения
- 1≤T≤1,000
- 1≤N≤4
- 1≤Ci≤5 для каждого действительного i
Подзадачи
Подзадача №1 (1 балл): C1=C2=…=CN
Подзадача 2 (99 баллов): исходные ограничения.
Пример ввода
3
3
2 2 2
3
1 2 3
4
2 3 4 5
Пример вывода
4
3
7
Объяснение
Пример 1: поставьте первые две тарелки на конфорки, подождите две минуты, уберите обе тарелки и приготовьте последнюю на одной конфорке.
Пример 2. Поставьте первую и третью тарелки на конфорки. Когда первое блюдо будет готово, снимите его, а второе поставьте на ту же конфорку.
Пример 3: поставьте третью и четвертую посуду на конфорки. Когда третье блюдо будет готово, снимите его и поставьте второе блюдо на ту же конфорку. Точно так же замените четвертое блюдо (когда оно будет приготовлено) первым блюдом на другой конфорке.
Решение
#include <iostream> using namespace std; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } void selectionSort(int arr[], int n) { int i, j, min_idx; // One by one move boundary of unsorted subarray for (i = 0; i < n-1; i++) { // Find the minimum element in unsorted array min_idx = i; for (j = i+1; j < n; j++) if (arr[j] > arr[min_idx]) min_idx = j; // Swap the found minimum element with the first element swap(&arr[min_idx], &arr[i]); } } /* void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } */ int main() { int T,N,TT[4]; cin >> T; int k = T; while(k--){ cin >> N; for( int i = 0; i < N; i++) cin>>TT[i]; selectionSort( TT,N); // printArray( TT, N); int b1=0,b2=0; for(int i= 0; i< N; i++){ if(b1==b2) b1 += TT[i]; else if (b1>b2) b2 += TT[i]; else if(b2>b1) b1 += TT[i]; } cout << max(b1,b2)<< endl; } return 0; }