9.18 文远知行笔试2.5

100
// dfs 找最小
// 贪心 ！！！
// 或者动态规划？？？
#include <bits/stdc++.h>
using namespace std;
int main () {
    vector<int>arr;
    int a;
    while (scanf("%d,", &a) != EOF) {
        arr.push_back(a);
    }
    int len = arr.size();
    // 用贪心，每次跳到数字最大的位置！！
    if (len <= 1) {
        cout<<0<<endl;
        return 0;
    }
    int i = 0, cnt = 0;
    while (true) {
        if (i + arr[i] >= len - 1) {
            cnt++;
            break;
        }
        int maxNum = -1, maxIndex = -1;
        for (int j = i + 1; j <= i + arr[i]; ++j) {
            if (arr[j] + j >= maxNum + maxIndex) { // !!!! 这个贪心很重要
                maxNum = arr[j];
                maxIndex = j;
            }
        }
        i = maxIndex;
        cnt++;
    }
    cout<<cnt<<endl;
//     vector<int>dp(len, len);
//     dp[0] = 0;
//     for (int i = 1; i < len; ++i) {
//         for (int j = 0; j < i; ++j) {
//             if (arr[j] + j >= i) {
//                 dp[i] = min(dp[i], dp[j] + 1); // 由前面的状态扩展而来
//             }
//         }
//     }
//     cout<<dp[len - 1];

//     for (int i : arr) {
//         cout<<i<<endl;
//     }
    return 0;
}

一开始选取思路就有问题，哎，麻了，只过了50，我以为取最大值做dp会爆内存，之前做过类似的就爆内存了 #include <bits/stdc++.h>
using namespace std;
typedef struct course {
    int l, r;
    int val;
    course() : l(0), r(0), val(0) {}
}course;
bool cmp (course c1, course c2) {
    if (c1.l != c2.l) {
        return c1.l < c2.l;
    }
//     else {
//         if (c1.r != c2.r) {
//             return c1.r < c2.r;
//         }
//         return c1.val > c2.val;
//     }
    return c1.r < c2.r;
}
int main () {
    int n;
    cin>>n;
    vector<course>arr(n);
    for (int i = 0; i < n; ++i) {
        cin>>arr[i].l>>arr[i].r>>arr[i].val;
    }
    sort(arr.begin(), arr.end(), cmp);
//    vector<bool>dele(n, false);
//    int before = 0;
//    int remain = 0;
//    for (int i = 1; i < n; ++i) {
//        before = i - 1;
//        while (before >= 0 && dele[before]) {
//            before--;
//        }
//        while (before >= 0 && arr[i].l >= arr[before].l && arr[i].r <= arr[before].r && arr[i].val >= arr[before].val) {
//            dele[before] = true;
//            remain++;
//            before--;
//        }
//    }
//    remain = n - remain;
//    vector<course>arr2(n);
//    int cc = 0;
//    for (int i = 0; i < n; ++i) {
//        if (dele[i]) {
//            continue;
//        }
//        arr2[cc] = arr[i];
//        ++cc;
//    }
    vector<long long>dp(n, 0);
    dp[0] = arr[0].val;
    long long res = 0;
    int index = 0;
    bool flag = false;
    for (int i = 1; i < n; ++i) {
        dp[i] = arr[i].val;
        index = i - 1;
        flag = false;
        while (index >= 0) {
            if (arr[index].r <= arr[i].l && dp[index] + arr[i].val > dp[i]) {
                // 更新
                flag = true;
                dp[i] = dp[index] + arr[i].val;
            }
//             if (flag && index > 0 && arr[index].l > arr[index - 1].r && dp[index] > dp[index - 1]) {
//                 break;
//             }
            --index;
        }
        res = max(res, dp[i]);
    }
//     for (long long i : dp) {
//         res = max(res, i);
//     }
    cout<<res<<endl;
    return 0;
}

100
#include <bits/stdc++.h>
using namespace std;
// 相当于求最小值
// 用最小堆！！！然后给他相加，再扔回去！！要超时！！
// 二分check!! 是否满足！！n 比较小！！！
bool check(long long cnt, vector<long long> &arr, long long m) {
    for (long long i : arr) {
        if (i < cnt) {
            m = m - (cnt - i);
            if (m < 0) {
                return false;
            }
        }
    }
    return true;
}
int main () {
    int n;
    long long m;
    cin>>n>>m;
    vector<long long>arr(n, 0);
    long long l = 0, r = 0;
    for (int i = 0; i < n; ++i) {
        cin>>arr[i];
        r = max(r, arr[i]);
    }
    r = r + m / n; // 一定要加这行！！！
    long long mid = 0;
    long long res = 0;
    while (l <= r) {
        mid = l + ((r - l) >> 1);
        if (check(mid, arr, m)) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    cout<<(res == 0 ? -1 : res)<<endl;
    return 0;
}