30/09/2018, 19:31

Anh chị xem dùm em sai chỗ nào mà kết quả lại sai ạ :(

Đề bài: Công ty tin học XYZ quyết định thuê K xe chở hàng có tải trọng như nhau để vận chuyển các container hàng. Có n kiện hàng được bốc dỡ lần lượt theo thứ tự từ 1 đến n, kiện hàng thứ i
có trọng lượng ai. Hỏi rằng công ty cần thuê loại xe có tải trọng nhỏ nhất là bao nhiêu để cho
thể vận chuyển hết số hàng?
Input:
 Dòng đầu tiên ghi hai số nguyên n m K (1≤n≤105, 1≤K≤n)
 Các dòng tiếp theo lần lượt ghi các số nguyên dương a1, a2, …, an (ai≤109) Hai số liên
tiếp trên cùng một dòng ghi cách nhau ít nhất một dấu cách.
Output:
Một số nguyên duy nhất là tải trọng tối thiểu của K xe tải.
VD: inp: 5 2
3 2 4 5 1
out: 9

Code của em:

#include <bits/stdc++.h>

using namespace std;
ifstream fi("TRUCK.INP");
ofstream fo("TRUCK.OUT");

int n, k, a[100001], t, res, l, r;
bool check(int mid)
{
    int t1=0, c=0;
    for (int i=1; i<=n; i++)
    {
        if (t1+a[i]<=mid)
            t1+=a[i];
        else{
            t1=a[i];
            c++;
        }
    }
    c++;
    if (c>k) return false;
    else
    {
        res=mid;
        return true;
    }
}
void tknp()
{
    l=1, r=t;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid)) r=mid-1;
        else l=mid+1;
    }
    fo << res;
}
int main()
{
    fi >> n >> k;
    for (int i=1; i<=n; i++)
    {
        fi >> a[i];
        t+=a[i];
    }
    sort (a+1, a+1+n);
    tknp();
    fi.close(); fo.close();
}
Bài liên quan
0