蟻本 | 2-2 猪突猛進! "貪欲法"
硬貨の問題 const int v[6] = {1, 5, 10, 50, 100, 500}; int c[6]; int A; void solve() { int ans = 0; for (int i = 5; i >= 0; --i) { int t = min(A / v[i], c[i]); A -= t * v[i]; ans += t; } printf("%d\n", ans); } ```cpp ### 区間スケジューリング問題 ```cpp const int MAX_N = 100000; int N, s[MAX_N], t[MAX_N]; pair<int, int> itv[MAX_N]; void solve() { for (int i = 0; i < N; ++i) { itv[i].first = t[i]; itv[i].second = s[i]; } sort(itv, itv + N); int ans = 0; int t = 0; for (int i = 0; i < N; ++i) { if (t < itv[i].second) { t = itv[i].first; ans++; } } printf("%d\n", ans); } ```cpp ### Best Cow Line ```cpp int N; char s[100000]; void solve() { cin >> N; for (int i = 0; i < N; ++i) { cin >> s[i]; } int a = 0, b = N - 1; while (a <= b) { //左からと右からを比較 bool left = false; for (int i = 0; a + i <= b; ++i) { if (s[a + i] < s[b - i]) { left = true; break; } else if (s[a + i] > s[b - i]) { left = false; break; } } if (left) { putchar(s[a++]); } else { putchar(s[b--]); } } putchar('\n'); } ```cpp ### Saruman's Army ```cpp int n, r; int x[1010]; void solve() { cin >> n >> r; for (int i = 0; i < n; ++i) { cin >> x[i]; } sort(x, x + n); int i = 0, ans = 0; while (i < n) { int s = x[i++]; while (i < n && x[i] <= s + r) { i++; } int p = x[i - 1]; while (i < n && x[i] <= p + r) { i++; } ans++; } printf("%d\n", ans); } ```cpp ### Fence Repair ```cpp int n, l[50010]; void solve() { cin >> n; for (int i = 0; i < n; ++i) { cin >> l[i]; } LL ans = 0; while (n > 1) { int mii1 = 0, mii2 = 1; if (l[mii1] > l[mii2]) { swap(mii1, mii2); } for (int i = 2; i < n; ++i) { if (l[i] < l[mii1]) { mii2 = mii1; mii1 = i; } else if (l[i] < l[mii2]) { mii2 = i; } } int t = l[mii1] + l[mii2]; ans += t; if (mii1 == n - 1) { swap(mii1, mii2); } l[mii1] = t; l[mii2] = l[n - 1]; n--; } printf("%lld\n", ans); } ```cpp