题意分析

题目要求银行从贷款申请中选择子集，使得总利润最大。每个贷款申请有两个属性：利润p和截止时间d（贷款需在0到d的某个时间点处理）。银行每天最多处理L笔贷款，目标是计算可获得的最大利润。

解题思路

问题建模

这是一个典型的带截止时间的任务调度问题，核心是在有限的时间资源下选择利润最高的任务集合。关键思路如下：

1. 贪心策略：优先选择利润高的贷款，因为利润是优化目标。
2. 时间分配：对于每个贷款，尽量安排在最晚的可行时间点（截止时间），以释放更早的时间点给其他贷款。
3. 冲突处理：若截止时间已被占满（当天处理数达到L），则向前寻找最近的可用时间点。

算法步骤

1. 输入处理：读取贷款数量n和每日最大处理量L，以及每笔贷款的利润p和截止时间d。
2. 排序：按利润从高到低排序贷款，确保优先处理高利润贷款。
3. 时间分配：
   • 对每笔贷款，从其截止时间d开始检查当天是否可处理（已处理数<L）。
   • 若不可处理，向前移动一天（d--），直到找到可用时间点或时间点<0（无法处理）。
4. 计算总利润：累加所有成功安排的贷款利润。

代码逻辑解析

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

class T {
    public:
    int p;  // 利润
    int d;  // 截止时间
} loan[10010];  // 存储贷款信息
int counter[10010];  // counter[i]记录第i天已处理的贷款数

// 按利润从大到小排序
bool cmp(T a, T b) {
    return a.p > b.p;
}

int main() {
    int n, L;  // n为贷款数，L为每日最大处理量
    while (~scanf("%d%d", &n, &L)) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &loan[i].p, &loan[i].d);
        }
        memset(counter, 0, sizeof(counter));  // 初始化每日处理数为0
        sort(loan, loan + n, cmp);  // 按利润降序排序
        
        int profit = 0;  // 总利润
        for (int i = 0; i < n; i++) {
            // 寻找可用时间点（从截止时间向前找）
            int day = loan[i].d;
            while (counter[day] == L && day >= 0) {
                day--;
            }
            if (day < 0) continue;  // 无可用时间，跳过
            counter[day]++;  // 占用该时间点
            profit += loan[i].p;  // 累加利润
        }
        printf("%d\n", profit);  // 输出最大利润
    }
    return 0;
}

关键步骤说明

1. 贪心排序：
   通过cmp函数将贷款按利润从高到低排序，保证优先处理高利润贷款，这是贪心策略的核心。

2. 时间点分配：

   • 对每笔贷款，从截止时间d开始检查counter[day]是否小于L。
   • 若已满（counter[day] == L），则day--，直到找到可用时间点或day < 0。
   • 这种“最晚可用时间”策略避免了过早占用时间点，为其他贷款留出更多选择空间。

3. 边界处理：

   • 当L=0时，无法处理任何贷款，直接输出0。
   • 当day < 0时，贷款无法在截止时间内处理，跳过该贷款。

算法正确性证明

• 贪心策略有效性：
  高利润贷款优先处理可保证总利润最大化。若存在两个贷款A（p=5,d=2）和B（p=4,d=1），优先处理A更优，因为即使A占用d=2，B仍可能安排在d=1。

• 时间分配合理性：
  从截止时间向前找可用时间点，确保不浪费更早的时间点。例如，若d=2的时间点已满，尝试d=1，再d=0，这样更早的时间点可留给其他截止时间更小的贷款。

示例解析

以输入数据1为例：

4 1  
4 2  1 0  2 0  3 1  

1. 贷款按利润排序后为：(4,2), (3,1), (2,0), (1,0)。
2. 处理过程：
   • (4,2)：d=2，counter[2]=0<1，安排在day=2，profit=4。
   • (3,1)：d=1，counter[1]=0<1，安排在day=1，profit=7。
   • (2,0)：d=0，counter[0]=0<1，安排在day=0，profit=9。
   • (1,0)：d=0，counter[0]=1==1，day--到-1，无法处理。
3. 最终总利润为9，与样例输出一致。

复杂度分析

• 时间复杂度：

  • 排序：(O(n \log n))，n为贷款数（(n \leq 10000)）。
  • 时间分配：每笔贷款最多向前查找d次（(d \leq 10000)），总时间为(O(n \cdot d))。
    总体复杂度为(O(n \log n + n \cdot d))，适用于题目约束。

• 空间复杂度：

  • loan数组：(O(n))。
  • counter数组：(O(\max(d)))，(\max(d) \leq 10000)。
    总体空间复杂度为(O(n + 10000))，可接受。

总结

该算法通过贪心排序和“最晚可用时间”策略，高效解决了带截止时间的任务调度问题，确保在每日处理量限制下最大化总利润。代码逻辑简洁，边界处理完善，能够正确处理所有合法输入。