Cho n đoạn dây điện (1 ≤ n ≤ 105). Đoạn dây thứ i có độ dài ai (0 <ai≤ 109). Cần phải cắt các đoạn đã cho thành các đoạn sao cho có được K đoạn dây bằng nhau có độ dài nguyên. Có thể không cần cắt hết các đoạn dây đã cho. Mỗi đoạn dây bị cắt có thể có phần còn thừa khác 0.
Yêu cầu: Xác định độ dài lớn nhất của đoạn dây có thể nhận được. Nếu không có cách cắt thì đưa ra số 0.
Dữ liệu: file văn bản WIRES.INP có cấu trúc
- Dòng đầu tiên chứa hai số nguyên N, K
- Dòng thứ i trong N dòng tiếp theo chứa số nguyên ai
Kết quả: Đưa ra file văn bản WIRES.OUT,
- Một dòng duy nhất ghi độ dài lớn nhất có thể nhận được.
In theo kiểu tập tin pascal
|
WIRES.INP |
WIRES.OUT |
|
4 11 802 743 547 539 |
200 |
Bạn gửi email cho mình để mình gửi đáp án của bài này nhé.
#include<bits/stdc++.h>
#define FORn(i, n) for(int i=1; i<=(n); i++)
using namespace std;
int n, k, a[100005]={}, l=1, r=0;
bool kt(int x){
int dem=0;
FORn(i, n) dem+=a[i]/x;
return dem>=k;
}
int main(){
cin>>n>>k;
FORn(i, n){
cin>>a[i];
r=max(r, a[i]);
}
while(l<=r){
int mid=(l+r)/2;
if(kt(mid)) l=mid+1;
else r=mid-1;
}
cout<<l-1;
}
bạn nào dịch sang pascal giùm mk với :'(
program wires;
uses crt;
var i,n,k,l,r,mid,dem:integer;
a:array[1..100005] of integer;
kt:boolean;
begin
clrscr;
l:=1; r:=0; dem:=0;
read(n); read(k);
for i:=1 to n do
begin
read(a[i]);
if (a[i]>r) then r:=a[i]
end;
while (l<=r) do
begin
mid:=(l+r) div 2;
for i:=1 to n do dem:=dem+(a[i] div mid);
if (dem>=k) then kt:=true;
if (kt=true) then l:=mid+1 else r:=mid-1;
end;
write(l-1);
readln
end.
Cái này mới đúng nè =))
program wires;
uses crt;
var i,n,k,l,r,mid,dem:integer;
a:array[1..100005] of integer;
kt:boolean;
begin
clrscr;
l:=1; r:=0; dem:=0;
read(n); read(k);
for i:=1 to n do
begin
read(a[i]);
if (a[i]>r) then r:=a[i]
end;
while (l<=r) do
begin
mid:=(l+r) div 2;
for i:=1 to n do dem:=dem+(a[i] div mid);
if (dem>=k) then kt:=true;
if (kt=true) then l:=mid+1 else begin kt:=false; r:=mid-1; end;
end;
write((l-1)/2:0:0); delay (5000);
readln
end.
bạn tính nếu chia k đoạn bằng nhau thì đoạn dây có thể lấy gt lớn nhất là bao nhiêu bằng cách lấy sum/k;
rồi duyệt ngược x từ sum/k -> 1 , với mỗi giá trị kiểm tra xem có thỏa manx chia đủ k dây không,nếu thỏa mãn thì break rồi cout << x thôi
