HSG9 Phú Thọ 2026 - Hiệu lớn nhất

Điểm: 10,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Cho dãy số nguyên ~a_1, a_2, ..., a_n~ và số nguyên dương ~k~.

Yêu cầu: Thực hiện phép xóa ~k~ phần tử sao cho chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ còn lại là lớn nhất.

Input

Dòng đầu chứa hai số nguyên dương ~n, k~ (~k \le n - 2~).
Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~).

Output

Ghi ra một số duy nhất là giá trị lớn nhất tìm được.

Sample Input 1

5 1
4 1 2 3 9

Sample Output 1

Giải thích: Xóa 1 phần tử bất kỳ, thì dãy còn lại luôn tồn tại 2 số tự nhiên liên tiếp nhau, nên độ chênh lệch nhỏ nhất là 1.

Sample Input 2

5 2
10 -5 3 -2 1

Sample Output 2

Giải thích: Trong các cách xóa 2 phần tử bất kỳ, cách xóa còn 3 phần tử ~\{10, -5, 3\}~ có độ chênh lệch nhỏ nhất là 7. Cách xóa này là cách xóa có độ chênh lệch nhỏ nhất giữa các phần tử là lớn nhất.

Subtasks

Subtask 1 (20% số điểm): ~n \le 20, k = 1~.
Subtask 2 (30% số điểm): ~20 < n \le 100~.
Subtask 3 (25% số điểm): ~100 < n \le 2000~.
Subtask 4 (25% số điểm): ~2000 < n \le 10^5~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

tikl20tok đã bình luận lúc 28, Tháng 2, 2026, 15:59

Luu y: Do la loi cu phap khi web bien dich nen khi vao codeblock thi moi nguoi tu sua nhe. Xin cam on.

tikl20tok đã bình luận lúc 28, Tháng 2, 2026, 15:57

include<bits/stdc++.h>

using namespace std; bool a[(long long)1e6+10];

int main() {

ios::sync_with_stdio(false);
cin.tie(NULL);

long long n,k;
cin>>n>>k;
long long i,j;
vector&lt;long long> a;
a.reserve(n+5);
a.push_back(0);
for (i=1;i<=n;i++)
{
    cin>>j;
    a.push_back(j);
}
sort(a.begin()+1,a.end());
//chat nhi phan
long long start=1,en=1e9,mid;
long long bestone=-2e18;
while(start<=en)//chat nhi phan
{
    mid=start+(en-start)/2;
    j=1;
    bool kt=false;
    long long demok=0;
    for (i=2;i<=n;i++)
    {
        if (a[i]-a[j]>=mid)
        {
            demok+=1;
            j=i;//quay nguoc lai voi tinh chat de bai
            //de bai yeu cau moi cap i j trong tap hop phai lon hon hoac = mid (dung hon la cai nho nhat)
            //tu day ta suy ra duoc i j thi ta luon phai chon 2 cap sat nut nhau nhat co the
            //ta dat j=i o day la de toi uu khong gian (tim hieu them va kadane algorithm se hieu)
            //no se tuong tu kadane nhung 70% la khac nhau
        }
    }
    if (demok>=n-k-1)//demok la phan tu thoa man nhung chua bao gom moc doc tien
    //dieu do co nghia la demok+1>=n-k, sau do bien doi nhu tren
    {
        kt=true;
        bestone=max(bestone,mid);
    }

    if (kt==true)
    {
        start=mid+1;
    }
    else
    {
        en=mid-1;
    }

}
cout<&lt;bestone;






return 0;

}

day la code neu code ma bien dich loi thi la loi cu phap do web comply sai nhe

-6

tiendzvd2k11 đã bình luận lúc 7, Tháng 2, 2026, 9:31

n=int(input()) ...xem thêm

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.