望远镜调度动态规划代码问题：部分测试用例无法通过

Let's break down why your code is failing some test cases and fix the issues step by step.

Main Issue: Flawed Binary Search Logic #

The core problem lies in how you're trying to find the last non-conflicting interval using binary search. Your current logic relies on a found flag and checks arr[mid+1].F <= arr[i].S, which breaks in two key scenarios:

1. All previous intervals are non-conflicting: When every interval before i has F <= arr[i].S, your code will keep moving lo forward until it exceeds hi, leaving found as false—even though the last interval (index i-1) is valid. This means you'll miss adding its value to inclDesireability.
2. Current interval has equal start and end time: If arr[i].S == arr[i].F, checking arr[mid+1].F <= arr[i].S will always be true for mid = i-1 (since arr[i].F == arr[i].S), causing lo to jump to i and the loop to exit without setting found to true.

Fix for Binary Search #

Instead of using a found flag, we should track the last valid interval index directly. Here's the corrected approach:

• Initialize l = -1 (indicating no valid interval found initially).
• During each binary search iteration, if arr[mid].F <= arr[i].S, update l to mid and continue searching the right half to find a later valid interval.
• If arr[mid].F > arr[i].S, search the left half.

Other Minor Issues #

• Typos: comparataor is misspelled (should be comparator—while this doesn't break the code, it's better to use standard naming for readability).
• Uninitialized Variable: long long int l; is declared but only assigned if found is true. While this doesn't cause issues in your current flow, it's risky and can lead to undefined behavior if the logic ever changes.
• Boolean Clarity: Using false instead of 0 for boolean variables makes the code more readable.

Corrected Code #

#include <iostream>
#include <algorithm>
using namespace std;

struct Star { int S, F, D; };

bool comparator(Star s1, Star s2) { 
    return s1.F < s2.F; 
}

int main() {
    long long int N;
    cin >> N;
    
    Star* arr = new Star[N];
    for (long long i = 0; i < N; ++i) {
        cin >> arr[i].S >> arr[i].F >> arr[i].D;
    }
    
    sort(arr, arr + N, comparator);
    
    long long int* table = new long long int[N];
    table[0] = arr[0].D;
    
    for (long long int i = 1; i < N; ++i) {
        long long int inclDesireability = arr[i].D;
        long long int l = -1;
        long long int lo = 0, hi = i - 1;
        
        while (lo <= hi) {
            long long int mid = lo + (hi - lo) / 2; // Avoid potential overflow
            if (arr[mid].F <= arr[i].S) {
                l = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        if (l != -1) {
            inclDesireability += table[l];
        }
        
        table[i] = max(inclDesireability, table[i-1]);
    }
    
    cout << table[N-1] << endl;
    
    delete[] table;
    delete[] arr;
    return 0;
}

Key Improvements: #

1. Robust Binary Search: Correctly finds the last non-conflicting interval every time, even when all previous intervals are valid or the current interval has equal start/end times.
2. Overflow Protection: Used lo + (hi - lo)/2 instead of (lo + hi)/2 to prevent integer overflow for very large values of N.
3. Readability: Fixed naming, initialized variables properly, and used clearer boolean semantics.

内容的提问来源于stack exchange，提问作者galik