8 条题解
-
1
// https://dashoj.com/p/89 #include <bits/stdc++.h> #define N 1000010 using namespace std; typedef long long ll; ll n, m, ans; // 树木数量 需要木材总长度 答案 vector<ll> ls; // 输入长度列表 ll addd(int x) { ll re = 0; for (int i = 0; i < n; i++) if (ls[i] > x) re += ls[i] - x; return re; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); cin >> n >> m; for (int i = 0; i < n; i++) { ll a; cin >> a; ls.push_back(a); } sort(ls.begin(), ls.end()); ll l = 0, r = ls[n - 1]; while (l <= r) { ll mid = (l + r) >> 1; if (addd(mid) < m) r = mid - 1; else { ans = mid; l = mid + 1; } } cout << ans << endl; return 0; }
-
1
#include<bits/stdc++.h> using namespace std; using ll=long long; int n; const int N=1e6+5; ll m,a[N]; bool check(ll mid){ ll sum=0; for(int i=1;i<=n;i++){ if(a[i]-mid<=0){//如果该树高<=砍树高度,直接跳过 continue; } sum+=(a[i]-mid); } if(sum>=m){//当sum>=m说明砍树的高度要<=该mid return true; } return false; } int main(){ cin>>n>>m; ll maxx=0; for(int i=1;i<=n;i++){ cin>>a[i]; maxx=max(maxx,a[i]); } sort(a+1,a+1+n);//先排序 ll l=1,r=maxx,ans=0; while (r - l > 1) // 当右边界与左边界相差大于1时 { int mid = (l + r) >> 1; // 取中间位置 if (check(mid)){ // 如果满足条件 ans=mid;//最后得到的mid就是答案 l = mid; // 更新左边界为mid } else{ r = mid; // 否则更新右边界为mid } } cout<<ans<<endl; return 0; }
-
0
#include <iostream> using namespace std; int a[1000010]; int main() { cin.tie(0); cout.tie(0); long long n, m, max = -1, u = 0, x = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; if (max < a[i]) { max = a[i]; } } long long l = 0, r = max; while (l <= r) { u = 0; int mid = (l + r) / 2; for (int i = 1; i <= n; i++) { if (a[i] > mid) { u += a[i] - mid; } } if (u >= m) { x = mid; l = mid + 1; } else { r = mid - 1; } } cout << x; return 0; }
-
0
#include <bits/stdc++.h> using namespace std; const int N=1e6+10; int n,m; int a[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } int l=0,r=2e9; while(l<r){ int mid=(l+r+1)/2; long long sum=0; for(int i=1;i<=n;i++){ if(a[i]-mid>0) sum+=a[i]-mid; } if(sum>=m) l=mid; else r=mid-1; } cout<<l<<endl; }
-
0
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef pair<int,int> PII; using ll = long long; using ULL = unsigned long long; const int N = 1e6+5; ll n ,m, a[N]; bool check(ll mid) { ll sum = 0; for (int i = 0; i < n; i++) if (a[i] > mid) sum += a[i] - mid; return sum >= m; } inline void solve() { cin >> n >> m; ll l = 0, r = 0; for (int i = 0; i < n; i++) { cin >> a[i]; r = max(r,a[i]); } while (l < r) { ll mid = (l + r + 1) >> 1; if (check(mid)) l = mid; else r = mid -1; } cout << l << endl; } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _ = 1; //int _; cin >> _; while (_--) solve(); return 0; }
-
0
def get_wood_amount(trees, cut_height): # 计算砍下的木材总长度 wood = sum(tree - cut_height for tree in trees if tree > cut_height) return wood def find_max_height(trees, m): low, high = 0, max(trees) result = 0 while low <= high: mid = (low + high) // 2 wood = get_wood_amount(trees, mid) if wood >= m: result = mid low = mid + 1 else: high = mid - 1 return result # 读取输入 n, m = map(int, input().split()) trees = list(map(int, input().split())) # 计算结果 max_cut_height = find_max_height(trees, m) # 输出结果 print(max_cut_height)
-
0
普普通通二分题
我叫你开longlong你二龙嘛#define _CRT_SECURE_NO_WARNINGS 1 /** * @brief 打开宏开关 * */ #define _USE_MATH_DEFINES #include <cmath> #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 5; ll n, m; ll a[N]; bool bisearch(ll h) { ll sum = 0; for (int i = 1; i <= n; i++) { if (a[i] > h) sum += a[i] - h; } return sum >= m; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; ll l = 1, r = 1e9; while (l + 1 < r) { ll m = l + r >> 1; if (bisearch(m)) l = m; else r = m; } if (bisearch(l)) cout << l; else cout << r; return 0; }
-
0
二分答案即可
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int a[N]; int n,m; int mx = -1; bool check(int x){ long long sum = 0; for (int i = 1; i <= n; ++i) { if (a[i] > x) { sum += (a[i] - x); }else{ continue; } } if (sum < m) return true; return false; } int main(){ scanf("%d %d",&n,&m); for (int i = 1; i <= n; ++i) { scanf("%d",&a[i]); mx = max(mx,a[i]); } int l = 1,r = mx; while (l + 1 < r) { int mid = (l + r)/2; if (check(mid)) { r = mid; }else { l = mid; } } printf("%d\n",l); return 0; }
- 1
信息
- ID
- 89
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1686
- 已通过
- 363
- 上传者