OJ Board

Code: Select all

/**
 * 11292 - Dragon of Loowater
 * author: Dennis Ideler
 * category: greedy
 */

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

int main()
{
  // knight height >= head diameter
  // wage = height
  // minimize expenses (i.e. choose shortest knights possible)

  long n, m; // n = dragon heads, m = knights
  while (cin >> n >> m)
  {
    if (n == 0 && m == 0) break;

    long dd[n]; // dragon diameter
    for (long i = 0; i < n; i++)  // read diameter of each dragon head
      cin >> dd[i];

    long kh[m]; // knight height
    for (long i = 0; i < m; i++)  // read height of each knight
      cin >> kh[i];

    if (n <= 0)
    {
      cout << "0" << endl;
    }
    if (n > m || m <= 0)
    {
      cout << "Loowater is doomed!" << endl;
      continue;
    }

    // find minimum number of gold coins needed for the job
    sort(dd, dd + n);
    sort(kh, kh + m); // sorted data makes comparison easier

    long gold = 0;
    long j = 0;
    bool doom = false;
    for (long i = 0; i < n; ++i) // for each dragon head
    {
      for (; j < m; ++j) // for each knight
      {
        if (dd[i] <= kh[j])  // knight is capable
        {
          gold += kh[j];  // assign knight
          break; // go to next dragon head
        }
        if (j == m-1) // no knight capable
        {
          doom = true;
          cout << "Loowater is doomed!" << endl;
        }
      }
    }
    if (!doom)  // if all dragon heads slain
      cout << gold << endl;
  }

  return 0;
}

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define max 20000

int compare(const void  * a, const void * b)
{
    return(*(int*)a - *(int*)b);
}

int main(){
    int diameter[max];
    int height[max];
    int drHead = 0;
    int knight = 0;
    int i,j;
    int sum = 0;
    int killed=0;

    while(scanf("%d %d", &drHead, &knight), drHead, knight){
    for(i=0; i<drHead; i++)
      scanf("%d", &diameter[i]);
      
    for(i=0; i<knight; i++)
      scanf("%d", &height[i]);
      
      qsort(diameter, drHead, sizeof(int), compare);
      qsort(height, knight, sizeof(int), compare);
      
      for(i=0; i<knight; i++)
        for(j=0; j<drHead; j++)
        {
          if (height[i] >= diameter[i])
	         diameter[i] = 0;
        }
	         
    for(i=0; i< drHead; i++)
      sum = sum + diameter[i];
	         
    if(sum == 0)
      killed = 1;
    else
      killed = 0;
      
    if(knight < drHead || killed == 0)
        printf("Loowater is doomed!\n");
    else
    {
      for(i=0;i<drHead;i++)
        sum = sum + height[i];
        printf("%d\n", sum);
      }   
    }

    return 0;
}

Code: Select all

#include <iostream>
#include <algorithm>

using namespace std;

int main () {
	int n, m; 
	long hd[20000], kh[20000];
	while ( cin >> n >> m && n != 0 && m != 0 ) {
		long pay = 0;
		for ( int i = 0; i < n; i++ ) {
			cin >> hd[i];
		}
		sort( hd, hd + n );
		for ( int i = 0; i < m; i++ ) {
			cin >> kh[i];
		}
		sort ( kh, kh + m );
		if ( n > m ) {
			cout << "Loowater is doomed!" << endl;
			continue;
		}
		int flag = 0, headcount = n;
		for ( int i = 0; i < n; i++ ) {
			for ( int j = flag; j < m; j++ ) {
				if ( kh[j] >= hd[i] ) {
					flag = j;
					pay += kh[j];
					headcount--;
					break;
				}
			}
		}
		if ( headcount > 0 ) {
			cout << "Loowater is doomed!" << endl;
		}
		else {
			cout << pay << endl;
		}
	}
	return 0;
}