Nguồn đề bài: http://vn.spoj.com/problems/CBUYING/
Nội dung bài viết
1. Đề bài CBUYING spoj
Những con bò rất thích ăn Sô-cô-la , nên Farmer John quyết định mua một ít cho chúng.
Cửa hàng có N loại sô-cô-la (được đánh số từ 1..N) với số lượng mỗi loại không hạn chế. Loại thứ i có giá P_i($$) và có đúng C_i con bò muốn ăn loại Sô-cô-la ấy. Farmer John có B $$ để mua Sô-cô-la cho lũ bò.
Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu ? Biết rằng mỗi con bò chỉ thích một loại sô-cô -la, và nó chỉ được ăn loại sô-cô-la ấy.
Input
Dòng đầu tiên là hai số nguyên N và B.
N dòng tiếp theo , dòng thứ i+1 là hai số nguyên dương P_i và C_i.
Output
Gồm một số duy nhất là kết quả.
Example
Input:
5 50
5 3
1 1
10 4
7 2
60 1
Output:
8
Giới hạn
1<=N<=10^5
1 <= B <= 10^18
1 <= C_i <= 10^18
1 <= P_i <= 10^18.
Giải thích:
FJ sẽ mua như sau:
+Mua 3 gói sô-cô-la loại 1 mất 3*5= 15$.
+Mua 1 gói sô-cô-la loại 2 mất 1*1= 1$.
+Mua 2 gói sô-cô-la loại 3 mất 2*10= 20$
+Mua 2 gói sô-cô-la loại 4 mất 2*7= 14$.
Tổng cộng hết :15+1+20+14=50$, và FJ đã phục vụ được 8 con bò.
###################################################
2. Hướng dẫn CBUYING spoj
– Bạn sẽ dễ dàng nhận thấy, cứ ưu tiên mua cho những con bò có bánh yêu thích rẻ hơn thì bạn sẽ được khoản còn lại nhiều hơn. chính vì vậy ở đây chỉ cần sắp xếp C[i], P[i] theo P[i] là được. Tức là ưu tiên mua bánh giá rẽ trước 😀
– còn lại chỉ là tìm cách duyệt lấy kết quả thôi. các bạn có thể tham khảo cách mình viết.
3. Code tham khảo CBUYING spoj
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | const fi=''; type data=longint; var f:text; B:qword; N:data; C,P:array[0..100000+1] of qword; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n,b); for i:=1 to n do readln(f,p[i],c[i]); close(f); end; procedure sort(l,r: longint); var i,j: longint; x,y:qword; begin i:=l; j:=r; x:=p[(l+r) div 2]; repeat while p[i]<x do inc(i); while x<p[j] do dec(j); if not(i>j) then begin y:=p[i]; p[i]:=p[j]; p[j]:=y; y:=c[i]; c[i]:=c[j]; c[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure xuli; var i,j:data; res:qword; begin res:=0; for i:=1 to n do begin if b div p[i]>=c[i] then begin B:=B-(p[i]*c[i]); res:=res+c[i]; end else begin res:=res+b div p[i]; break; end; end; writeln(res); end; begin docfile; sort(1,n); xuli; end. |
Bài viết liên quan
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- P151PROG spoj PTIT – Xếp Hàng
- AUCTION spoj – Going Once, Going Twice, Gone
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P164SUMI spoj PTIT – ROUND 4I – Next round
- PTIT135J spoj PTIT – Tính lãi suất
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
Em viết thế này thì có gì sai hả anh? ==
#include
using namespace std;
typedef pair LL;
LL a[100001];
int n;
long long b, dem=0;
int main()
{
//freopen(“cbuying.inp”,”r”,stdin);
scanf(“%d%I64d”,&n,&b);
for(int i=1; i<=n; i++)
scanf("%I64d%I64d",&a[i].first,&a[i].second);
sort(a+1,a+n+1);
for(int i=1; i=a[i].second){
b=b-(long long)a[i].second*a[i].first;
dem+=(long long)a[i].second;
}
else {
dem+=(long long)p;
break;
}
}
printf(“%I64d”,dem);
}
submit bị sai à 😀
như bao ng 37,5 == vầy là lỗi gì hả anh?
em sort có đúng ko nhỉ 😀
em k biết! nhưng mà chắc là đúng đó! sort theo p mà! ^_^
Vâng. ai code bài này bằng C mà đc 37,5 thì dùng cin cout là AC đó. ==