为什么两个代码一个能过,一个过不了呢

一个是升序排列,从后向前枚举;另一段降序排列,从前向后枚举却只能过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;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 12:10
点赞 评论 收藏
分享
07-16 19:23
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务