C++14(g++5.4) 解法, 执行用时: 59ms, 内存消耗: 604K, 提交时间: 2019-08-30 22:21:39

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
struct edge {
    int a, b;
    edge() {}
    edge(int a, int b) : a(a), b(b) {}
    bool operator < (const edge &s) const {
        return s.a > a;
    }
}spt[MAXN];
int main() {
    int n, m, ans = 0;
    int cnt = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a >= m)
            ans += b;
        else spt[cnt++] = edge(a, b);
    }
    sort(spt, spt + cnt);
    while (true) {
        int x = m;
        for (int i = cnt - 1; ~i; i--) {
            if (spt[i].b && spt[i].a <= x)
                while (spt[i].b && spt[i].a <= x)
                    x -= spt[i].a, spt[i].b--;
        }
        if (x > 0) {
            for (int i = 0; i < cnt && x > 0; i++) {
                if (spt[i].b)
                    x -= spt[i].a, spt[i].b--;
            }
        }
        if (x > 0)
            break;
        ans++;
    }
    printf("%d\n", ans);
    return 0;
}

C++(clang++11) 解法, 执行用时: 37ms, 内存消耗: 504K, 提交时间: 2021-03-25 16:36:36

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
struct temp {
	int a;
	int b;
} t[21];

int cmp(temp x,temp y) {
	if(x.a>y.a)return 1;
	else return 0;
}

ll sum;
int main() {
	int n,c;
	cin>>n>>c;
	int k=0;
	int o=0;
	while(n--) {
		int v,m;
		cin>>v>>m;
		if(v>=c)sum+=m;
		else {
			t[k].a=v;
			t[k].b=m;
			o++;
			k++;

		}
	}
	sort(t,t+o,cmp);
	while(true) {
		int x=c;
		for(int i=0; i<o; i++) {
			while(x>=t[i].a&&t[i].b>0) {
				x-=t[i].a;
				t[i].b--;
			}
		}
		
		if(x>0){
			for(int j=o-1; j>=0; j--) {
			while(x>0&&t[j].b>0) {
				x-=t[j].a;
				t[j].b--;
			}
		}
		}
		if(x>0)break;
		sum++;
		
	}
	cout<<sum<<endl;
	return 0;


}