为什么两个代码一个能过,一个过不了呢
一个是升序排列,从后向前枚举;另一段降序排列,从前向后枚举却只能过75呢
AC:
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; typedef pair<int, int> PII; const int N = 2e5 + 10; ll n, s, L; ll h[N], a[N], c[N]; ll mx; bool check(ll d) { for (int i = 0; i < n; i ++ ) c[i] = h[i] + d * a[i]; //sort(c, c + n, greater<int>()); sort(c, c + n); ll sum = 0; for (int i = n - 1; i >= 0; i -- ) { if (c[i] < L) break; sum += c[i]; if (sum >= s) break; } if (sum >= s) return true; return false; } void solve() { cin >> n >> s >> L; for (int i = 0; i < n; i ++ ) cin >> h[i]; for (int i = 0; i < n; i ++ ) cin >> a[i]; for (int i = 0; i < n; i ++ ) { mx = max(mx, max(L, s) / a[i]); } ll l = 0, r = mx; while (l < r) { ll mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); //int t; cin >> t; while (t -- ) solve(); return 0; }
通过75:
#include <bits/stdc++.h> using namespace std; #define endl '\n' typedef long long ll; typedef pair<int, int> PII; const int N = 2e5 + 10; ll n, s, L; ll h[N], a[N], c[N]; ll mx; bool check(ll d) { for (int i = 0; i < n; i ++ ) c[i] = h[i] + d * a[i]; sort(c, c + n, greater<int>()); //sort(c, c + n); ll sum = 0; for (int i = 0; i < n; i ++ ) { if (c[i] < L) break; sum += c[i]; if (sum >= s) break; } if (sum >= s) return true; return false; } void solve() { cin >> n >> s >> L; for (int i = 0; i < n; i ++ ) cin >> h[i]; for (int i = 0; i < n; i ++ ) cin >> a[i]; for (int i = 0; i < n; i ++ ) { mx = max(mx, max(L, s) / a[i]); } ll l = 0, r = mx; while (l < r) { ll mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); //int t; cin >> t; while (t -- ) solve(); return 0; }