Đề THT B - BRVT - 2015: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2014 - 2015.

Bạn đọc có thể nộp và chấm bài (test tự sinh) TẠI ĐÂY.

Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)

• Đề THT B - BRVT - 2015: Editorial
  • Bài 1: Hệ trục tọa độ (20 điểm)
    • Tóm tắt đề bài
    • Lời giải
  • Bài 2: Phát thưởng (40 điểm)
    • Tóm tắt đề bài
    • Lời giải

Bài 1: Hệ trục tọa độ (20 điểm)

Tóm tắt đề bài

Cho một dãy số nguyên có

$n$ phần tử

$a_1,a_2,...,a_n$. Người ta biểu diễn

$n$ số nguyên đó trên trục hoành

$(x^{\prime }Ox)$.

Yêu cầu: Hãy cho biết phải cần dùng ít nhất bao nhiêu đơn vị độ dài trên trục

$x^{\prime }Ox$.

Dữ liệu đảm bảo:

• $1\le n\le {10}^6$.
• $|a_i|\le {10}^9$.

Lời giải

Nhận xét

Nếu biểu diễn các điểm lên hệ trục hoành (

$x^{\prime }Ox$), độ dài ít nhất cần dùng sẽ là độ chênh lệch giữa điểm có hoành độ nhỏ nhất và điểm có hoành độ lớn nhất.

BBài toán trở thành tính độ chênh lệch giữa điểm có hoành độ nhỏ nhất và điểm có hoành độ lớn nhất.

Chạy vòng lặp nhập vào hoành độ từng điểm, duy trì hai biến

$mi$ và

$ma$ lần lượt lưu hoành độ nhỏ nhất và lớn nhất.

Đáp án:

$ma-mi$.

Lưu ý: Khởi gán hai giá trị

$mi$ và

$ma$ là hoành độ của điểm đầu tiên hoặc bằng những giá trị vô cực.

Độ phức tạp thời gian:

$O\left(n\right)$.

Code

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

long long n, a[1000009], x, mi, ma;

int main() {
    cin >> n >> x;
    mi = ma = x;
    
    for (int i = 2; i <= n; ++i) {
        cin >> x;
        mi = min(mi, x);
        ma = max(ma, x);
    }
    
    cout << ma - mi;
    
    return 0;
}

Bài 2: Phát thưởng (40 điểm)

Tóm tắt đề bài

Cho

$n$ học sinh và

$m$ giá trị tiền thưởng.

$a_i$ thể hiện giá trị phần thưởng mà học sinh thứ

$i$ sẽ nhận được.

Yêu cầu: Tìm cách phát thưởng sao cho số lượng học sinh nhận thưởng là nhiều nhất và tổng giá trị phần thưởng không vượt quá lượng dự trù.

Dữ liệu đảm bảo:

• $1\le n\le {10}^5$.
• $1\le k\le {10}^{18}$.
• $1\le a_i\le {10}^9$.

Lời giải

Nhận xét

Để tối ưu số học sinh nhận giải, nên ưu tiên cho các học sinh nhận ít giải thưởng.

Sắp xếp giá trị phần thưởng của các em học sinh theo thứ tự từ bé đến lớn.

Tức là sắp xếp mảng

$a$ tăng dần.

Duyệt để tìm ra số

$x$ lớn nhất thỏa mãn:

$x\le n$ và

$a_1+a_2+\cdots +a_x\le k$.

Đó cũng chính là đáp án của bài toán.

Độ phức tạp thời gian:

$O(n\log n)$.

Code

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

long long n, a[100009], x, s, k;

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; ++i) {
        s += a[i];
        
        if (s <= k) {
            x = i;
        }
        else {
            break;
        }
    }
    
    cout << x;
    return 0;
}