Suhendry’s Blog

D - Noodle Team Contest

Problem: D - Noodle Team Contest
Author: Felix Halim

Kita diminta untuk mencari sebuah jadwal untuk N orang sehingga total waktu memasak mereka sekecil mungkin. Meskipun N cukup kecil, namun mencoba semua permutasi urutan (N!) akan menyebabkan TLE karena jumlah testcase yang cukup banyak.

Total waktu terkecil bisa didapatkan dengan pendekatan greedy berdasarkan waktu memasak step-2 secara menurun (yang lebih lama di step-2 lebih dulu memasak).

Misalkan:
f(A) adalah waktu yang diperlukan peserta A untuk memasak step-1 nya.
g(A) adalah waktu yang diperlukan peserta A untuk memasak step-2 nya.
h(A,B) artinya giliran B memasak langsung setelah A selesai.

Seandainya ada solusi optimal yang tidak mengikuti solusi greedy, artinya akan ada jadwal optimal dimana h(A,B) dan g(A) <= g(B). Mari kita perhatikan apa yang terjadi jika kita tukar urutan A dan B sehingga h(A,B) menjadi h(B,A).

Pada h(A,B), total waktu yang diperlukan adalah f(A) + max{g(A), f(B)+g(B)}. Karena g(A) <= g(B), maka h(A,B) = f(A) + f(B) + g(B). Jika urutan A dan B ditukar, maka total waktu yang diperlukan adalah h(B,A) = f(B) + max{g(B), f(A)+g(A)}. Jika kita kurangi kedua persamaan dengan f(B) dan g(B), maka h(A,B) menjadi f(A) dan h(B,A) menjadi 0 atau f(A)+g(A)-g(B). Karena g(A) <= g(B) maka jelas bahwa h(B,A) selalu lebih kecil atau sama dengan h(A,B).

Dari pengamatan di atas, jelas bahwa solusi optimal yang memiliki kasus h(A,B) dan g(A) &lt= g(B) dapat diubah menjadi h(B,A) mengikuti aturan greedy tanpa mengubah solusi optimalnya.

Solusi C/C++
oleh Felix Halim

#include <cstdio>
#include <algorithm>
using namespace std;

struct tdata { int one; int two; };
bool operator < (const tdata &a, const tdata &b) {
   return a.two > b.two;
}

int main(){
   int T;
   scanf( "%d", &T );
   while ( T-- ) {
      int n;
      tdata arr[20];tr
      scanf( "%d", &n );
      for ( int i = 0; i < n; i++ )
         scanf( "%d %d", &arr[i].one, &arr[i].two );
      sort(arr,arr+n);
      int pre = 0, res = 0;
      for (int i=0; i<n; i++){
         pre += arr[i].one;
         res = max(res, pre + arr[i].two);
      }
      printf("%d\n",res);
   }

   return 0;
}

• Problem A - General Election
• Problem B - Liar Game
• Problem C - Why is Math Book So Sad?
• Problem D - Noodle Team Contest
• Problem E - Palapa Number
• Problem F - New House

Pages: 1 2 3 4 5 6 7