---
# System prepended metadata

title: 12578 - Smart Thief
tags: [NTHUOJ]

---

# 12578 - Smart Thief
## 題解:
用greedy法,
先將value陣列由大到小排序, 從最大的開始拿
當sum > remaining就離開迴圈, 並計算數量
## Code:
```cpp
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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

int main(){
    int n, v[5005], rem = 0, sum = 0, ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &v[i]);
        rem += v[i];
    }
    qsort(v, n, sizeof(int), cmp);
    for (int i = 0; i < n; i++){
        if(sum > rem)
            break;
        sum += v[i];
        rem -= v[i];
        ans++;
    }
    printf("%d\n", ans);
}
```
###### tags: `NTHUOJ`