CBUYING – spoj

Đề bài:

Thuật toán:

  • Chọn số những sô cô la có giá rẻ nhất

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<ll,ll> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n;
ll ans, b;
PII a[MAXN];
 
bool cmp(PII a, PII b) {
    return (a.fi < b.fi);
}
 
int main() {
    cin >> n >> b;
    FOR(i,1,n) cin >> a[i].fi >> a[i].se;
    sort(a+1,a+n+1,cmp);
    FOR(i,1,n) {
        if (b < a[i].fi) break;
        ll tmp = b / a[i].fi;
        b -= min(tmp,a[i].se) * a[i].fi;
        ans += min(tmp,a[i].se);
    }
    cout << ans;
	return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*