Để hỗ trợ các bạn học sinh chuẩn bị tốt cho kỳ thi HSG cấp Thành phố sắp đến, thầy giáo bồi dưỡng chuẩn bị nn bài tập (1≤n≤105)(1≤n≤105). Các bài được đánh số

Câu hỏi :

Để hỗ trợ các bạn học sinh chuẩn bị tốt cho kỳ thi HSG cấp Thành phố sắp đến, thầy giáo bồi dưỡng chuẩn bị $n$ bài tập $(1 \leq n \leq 1 0^{5})$ . Các bài được đánh số từ $1$ đến $n$ . Mỗi bài tập nhằm rèn luyện một số kỹ năng cho thí sinh, ví dụ như kỹ thuật lập trình, giải thuật, cấu trúc dữ liệu…

Nhằm định hướng cho quá trình tự luyện tập được hiệu quả, mỗi bài tập có một yêu cầu tối thiểu về trình độ kỹ năng. Để giải được bài thứ $i$ , bạn cần có trình độ kỹ năng tối thiểu là $a_{i}$ . Điều này có nghĩa là học sinh có thể giải được bài thứ $i$ khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơn $a_{i}$ . Nếu giải được bài thứ $i$ trình độ kỹ năng của học sinh sẽ tăng thêm một lượng là $b_{i}$ $(1 \leq a_{i}, b_{i} \leq 1 0^{9})$ . Giả sử ban đầu, trình độ kỹ năng của bạn trước khi làm bài tập là $c$ $(0 \leq c \leq 1 0^{9})$ . Các bài tập có thể được làm theo trình tự bất kỳ tùy chọn.

Ví dụ, với trình độ kỹ năng ban đầu $c = 1, n = 4$ và các giá trị $a_{i}, b_{i}$ tương ứng là $(1, 10), (21, 5), (1, 10), (100, 100)$ , bạn sẽ giải bài $1$ , sau đó làm bài $3$ và cuối cùng làm bài $2$ . Như vậy bạn sẽ làm được tất cả là $3$ bài.

Yêu cầu: Cho các số nguyên $n, c$ và các cặp giá trị $(a_{i}, b_{i})$ , $1 \leq i \leq n$ . Hãy xác định số lượng bài tối đa có thể được giải.

Input

Dòng đầu tiên chứa 2 số nguyên $n$ và $c$ .

Dòng thứ $i$ trong $n$ dòng tiếp theo $(1 \leq i \leq n)$ chứa $2$ số nguyên $a_{i}$ và $b_{i}$ . Các số trên cùng một dòng được ghi cách nhau bởi $1$ khoảng trắng.

Output

Là một số nguyên xác định số lượng bài tối đa có thể được giải. mong đc giải bằng c++ ạ

Lời giải 1 :

#include <bits/stdc++.h>

using namespace std;

int64_t n, k;
int main()
{

 ios_base::sync_with_stdio(false);
 cin.tie(0);

 cin >> n >> k;
 vector<pair<int64_t, int64_t>> a(n);
 for (int64_t i = 0; i < n; ++i) cin >> a[i] . first >> a[i] . second;
 int64_t cnt = 0;
 sort (a . begin(), a . end());
 for (int64_t i = 0; i < n; ++i)
 {
    if (k < a[i] . first) break;
    else 
    {
        k += a[i] . second;
        cnt++;
    }
 }
 cout << cnt;
 return 0;
}

Lời giải 2 :

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct str{
	int require,skill;
}a[N];
int n,c;
bool compare(str ff,str ss){
	return ff.require<ss.require;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i].require>>a[i].skill;
	}
	sort(a+1,a+1+n,compare);
//	for(int i=1;i<=n;i++){
//		cout<<a[i].require<<"\n";
//	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(c>=a[i].require){
			c+=a[i].skill;
			++ans;
		}
		else break;
	}
	cout<<ans;
}
//By aerial

Bạn có biết?

Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!

Nguồn :

Wikipedia - Bách khoa toàn thư

Tâm sự lớp 8

Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần và sang năm lại là năm cuối cấp, áp lực lớn dần. Hãy chú ý đến sức khỏe, cân bằng giữa học và nghỉ ngơi để đạt hiệu quả tốt nhất!

Nguồn :

sưu tập

Để hỗ trợ các bạn học sinh chuẩn bị tốt cho kỳ thi HSG cấp Thành phố sắp đến, thầy giáo bồi dưỡng chuẩn bị nn bài tập (1≤n≤105)(1≤n≤105). Các bài được đánh số

Lời giải 1 :

Lời giải 2 :

Bạn có biết?

Nguồn :

Tâm sự lớp 8

Nguồn :

Có thể bạn quan tâm