sicily_1134 积木分发

sicily 贪心算法

题目链接

思路

贪心算法：让需求较少的人先完成积木，如果这样子也不能满足后面的人的需求的话，那就失败。

代码

// Problem#: 1134
#include<stdio.h>
int main() {
  int i, j1, j2, n;
  int s, a[10000 + 10] = { 0 }, b[10000 + 10] = { 0 };
  while (scanf("%d %d", &n, &s) && n) {
    for (i = 0; i < n; i++) scanf("%d %d", &a[i], &b[i]);
    for (j1 = 0; j1 < n; j1++) {
      for (j2 = j1; j2 < n; j2++) {
        if (b[j2] < b[j1]) {
          a[j2] ^= a[j1] ^= a[j2] ^= a[j1];
          b[j2] ^= b[j1] ^= b[j2] ^= b[j1];
        }
      }
    }
    for (i = 0; i < n; i++) {
      if (s >= b[i])
        s += a[i];
      else
        break;
    }
    printf(i == n ? "YES\n" : "NO\n");
  }
  return 0;
}