蟻本 | 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);
}

区間スケジューリング問題

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);
}

Best Cow Line

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');
}

Saruman’s Army

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);
}

Fence Repair

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);
}