Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

HVT_WOOD - Cắt gỗ

Nông dân Jonh cần phải cắt M mét gỗ để đem về làm chuồng bó cho đàn bò của mình. Bác có một cái máy cắt gỗ mới, vì vậy mà công việc chặt gỗ cũng chở lên dễ dàng hơn. Tuy nhiên, bác Jonh chỉ được phép để cắt các cây gỗ thành một hàng duy nhất.

Máy cắt gỗ của bác Jonh hoạt động như sau: bác thiết lập một tham số chiều cao H  (tính bằng mét), và máy sẽ cắt toàn bộ các cây có chiều cao lớn hơn H (tất nhiên, cây không cao hơn H mét vẫn còn nguyên vẹn). Sau đó bác chỉ chọn những phần cây bị cắt đứt. Ví dụ, nếu hàng cây chứa cây với chiều cao là 20, 15, 10, và 17 mét, và bác Jonh thiết lặp chiều cao là 15 mét, chiều cao các cây còn lại sau khi cắt sẽ là 15, 15, 10, và 15 mét, khi đó bác Jonh sẽ nhặt 5 mét của cây đầu tiên và 2 mét của cây thứ tư và có tổng số là 7 mét gỗ.

Bác Jonh là người tiết kiệm, vì vậy bác không muốn cắt gỗ nhiều hơn cần thiết. Vì vậy bác muốn thiết lập cho máy của mình chiều cao H càng cao càng tốt. Trợ giúp bác Jonh tìm số nguyên chiều cao tối đa của chiều cao H đề bác vẫn có thể cắt ít nhất là M mét gỗ.

Input

-       Dòng đầu tiên chứa 2 số nguyên dương N (1 ≤ N ≤ 106) là số lượng cây gỗ và M (1 ≤ M ≤ 2*109) là tổng độ dài mét gỗ cần khai thác.

- Dòng thứ hai chứa N số nguyên dương (nhỏ hơn 109) là chiều cao của mỗi cây gỗ (tính bằng mét). Dữ liệu vào luôn đảm bảo là bác Jonh có thể cắt được M mét gỗ.

Output

-         Một dòng duy nhất là chiều cao H lớn nhất cần thiết lập.

Example 1

Input:
4 7
20 15 10 17

Output:
15
Example 2
Input
5 20

4 42 40 26 46 


Output:
36
Submit solution!
Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-04-05
Thời gian chạy:1.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CPP JAVA PAS-GPC PAS-FPC
hide comments
2015-12-12 09:11:17
#include <bits/stdc++.h>

using namespace std;
long long a[1000001],n,m;
bool cmp(long long i, long long j)
{
return (i>j);
}
int main()
{
long long s=0;
cin >> n >> m;
for (long long i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+n+1,cmp);
for (long long i=a[1];i>=0;i--)
{
for (long long j=1;j<=n;j++)
{
if (a[j]>i) s+=(a[j]-i);
}
if (s==m)
{
cout << i;
return 0;
}
else s=0;
}

return 0;
}
2015-12-11 02:43:43
#include <bits/stdc++.h>

using namespace std;
int main()
{
int n,a[1000001],tong=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort (a+1,a+n+1);
for(int i=1,j=n;i<=n/2,j>=(n/2)+1;i++,j--)
tong+=a[i]+(a[j]-a[i])+a[j];

cout << tong << endl;
return 0;
}
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.