题解 ：

问题分析

这是一个经典的海盗分金币博弈问题，但增加了更复杂的投票规则$V_i$。我们需要为每个$i$（$1 \leq i \leq N$）计算：当有$i$个海盗时，最老的海盗能获得多少金币，或者是否会被扔下船。

核心思路：逆向动态规划

我们从最简单的子问题开始递推：

1. 当只有1个海盗时（$i=1$）：

   • 提案自动通过（因为只有自己）
   • 最老的海盗获得所有$K$枚金币
   • 状态：dp[1] = K，alive[1] = true

2. 当有$i$个海盗时（$i > 1$）：

   • 我们已经知道$i-1$个海盗时的结果
   • 第$i$个海盗（最老的）提出分配方案
   • 他需要获得至少$V_i$张同意票才能通过提案
   • 他自己肯定会投同意票（规则1：避免被扔下船）
   • 还需要$V_i - 1$个其他海盗投同意票

关键观察

设$prev\_coins[j]$表示当有$i-1$个海盗时，海盗$j$（按年龄排序，$1$最年轻）能获得的金币数，如果会被扔下船则为$-1$。

第$i$个海盗为了收买海盗$j$（$1 \leq j \leq i-1$），需要支付至少$prev\_coins[j] + 1$枚金币（如果$prev\_coins[j] \neq -1$），或者$0$枚金币（如果$prev\_coins[j] = -1$）。

优先级规则：最老的海盗会优先收买那些"性价比高"的海盗，即：

1. 收买成本低（需要支付的金币少）
2. 收买成本相同时，优先收买年龄大的（规则4）

算法设计

数据结构设计

我们需要维护每个海盗在子博弈中的预期收益。

typedef struct {
    long long coins;  // 能获得的金币数，-1表示被扔下船
    int id;           // 海盗编号（年龄顺序）
    int index;        // 在当前列表中的位置
} Pirate;

算法步骤

1. 初始化：只有1个海盗时，他获得所有金币
2. 从$i=2$到$N$逐步递推
3. 对于每个$i$： a. 获取$i-1$个海盗时的状态 b. 计算收买每个其他海盗的成本 c. 按照成本和年龄排序 d. 选择$V_i - 1$个成本最低的海盗进行收买 e. 计算最老海盗能保留的金币数 f. 如果金币不足，输出-1 g. 更新所有海盗在$i$人博弈中的状态

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_N 1000010

typedef long long ll;

// 海盗结构
typedef struct {
    ll cost;     // 收买这个海盗需要的金币
    int age;     // 海盗编号（年龄，1最年轻）
    int index;   // 在prev_coins中的索引
} PirateCost;

ll prev_coins[MAX_N];  // 上一个状态（i-1人）时每个海盗的金币
ll curr_coins[MAX_N];  // 当前状态（i人）时每个海盗的金币
int V[MAX_N];          // 通过提案需要的票数
int N;
ll K;

// 比较函数：按成本升序，成本相同时按年龄降序
int cmp_pirate_cost(const void *a, const void *b) {
    PirateCost *p1 = (PirateCost *)a;
    PirateCost *p2 = (PirateCost *)b;
    
    if (p1->cost < p2->cost) return -1;
    if (p1->cost > p2->cost) return 1;
    // 成本相同时，年龄大的优先
    return p2->age - p1->age;
}

// 计算i个海盗时，最老海盗能获得的金币数
ll solve_for_i(int i, ll *coins_result) {
    if (i == 1) {
        coins_result[1] = K;
        return K;
    }
    
    // 创建收买成本列表
    PirateCost *costs = (PirateCost *)malloc((i - 1) * sizeof(PirateCost));
    int cost_count = 0;
    
    for (int j = 1; j <= i - 1; j++) {
        if (prev_coins[j] == -1) {
            // 这个海盗在i-1人情况下会被扔下船
            // 收买他只需要0枚金币（规则1：避免被扔下船）
            costs[cost_count].cost = 0;
            costs[cost_count].age = j;
            costs[cost_count].index = j;
            cost_count++;
        } else {
            // 需要至少支付prev_coins[j] + 1枚金币
            costs[cost_count].cost = prev_coins[j] + 1;
            costs[cost_count].age = j;
            costs[cost_count].index = j;
            cost_count++;
        }
    }
    
    // 按成本排序
    qsort(costs, cost_count, sizeof(PirateCost), cmp_pirate_cost);
    
    // 最老的海盗需要V[i] - 1张其他海盗的同意票
    int votes_needed = V[i] - 1;
    
    // 计算总收买成本
    ll total_cost = 0;
    for (int j = 0; j < votes_needed && j < cost_count; j++) {
        total_cost += costs[j].cost;
    }
    
    // 如果需要的票数多于可收买的海盗数，或者总成本超过K
    if (votes_needed > cost_count || total_cost > K) {
        free(costs);
        return -1;  // 提案失败，最老海盗被扔下船
    }
    
    // 最老海盗能获得的金币
    ll elder_coins = K - total_cost;
    
    // 更新所有海盗在当前状态的金币数
    // 初始化：所有海盗默认进入下一轮子博弈
    for (int j = 1; j <= i - 1; j++) {
        coins_result[j] = prev_coins[j];
    }
    
    // 被收买的海盗获得金币
    for (int j = 0; j < votes_needed; j++) {
        int idx = costs[j].index;
        coins_result[idx] = costs[j].cost;
    }
    
    // 最老海盗的金币
    coins_result[i] = elder_coins;
    
    free(costs);
    return elder_coins;
}

int main() {
    scanf("%d %lld", &N, &K);
    
    for (int i = 1; i <= N; i++) {
        scanf("%d", &V[i]);
    }
    
    // 存储每个i的结果
    ll *results = (ll *)malloc((N + 1) * sizeof(ll));
    
    // 初始化：只有1个海盗的情况
    prev_coins[1] = K;
    results[1] = K;
    
    // 逐步递推
    for (int i = 2; i <= N; i++) {
        // 复制prev_coins到临时数组
        ll *temp_prev = (ll *)malloc((i) * sizeof(ll));
        for (int j = 1; j <= i - 1; j++) {
            temp_prev[j] = prev_coins[j];
        }
        
        // 计算i个海盗的情况
        ll *curr_state = (ll *)malloc((i + 1) * sizeof(ll));
        ll result = solve_for_i(i, curr_state);
        
        results[i] = result;
        
        // 如果提案失败，最老海盗被扔下船
        if (result == -1) {
            // 所有海盗进入i-1人子博弈
            for (int j = 1; j <= i; j++) {
                if (j == i) {
                    curr_state[j] = -1;  // 最老海盗被扔下船
                } else {
                    curr_state[j] = temp_prev[j];
                }
            }
        }
        
        // 更新prev_coins为当前状态
        free(prev_coins);
        prev_coins = (ll *)malloc((i + 1) * sizeof(ll));
        for (int j = 1; j <= i; j++) {
            prev_coins[j] = curr_state[j];
        }
        
        free(temp_prev);
        free(curr_state);
    }
    
    // 输出结果
    for (int i = 1; i <= N; i++) {
        printf("%lld\n", results[i]);
    }
    
    free(results);
    if (N > 0) free(prev_coins);
    
    return 0;
}

优化版本（更高效）

上面的实现为了清晰展示了算法逻辑，但内存分配较多。以下是优化版本：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000010

typedef long long ll;

typedef struct {
    ll cost;
    int age;
    int idx;
} PirateCost;

// 归并排序（稳定排序）
void merge(PirateCost *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    PirateCost *L = (PirateCost *)malloc(n1 * sizeof(PirateCost));
    PirateCost *R = (PirateCost *)malloc(n2 * sizeof(PirateCost));
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i].cost < R[j].cost || 
            (L[i].cost == R[j].cost && L[i].age > R[j].age)) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}

void merge_sort(PirateCost *arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int N;
    ll K;
    scanf("%d %lld", &N, &K);
    
    int V[MAX_N];
    for (int i = 1; i <= N; i++) {
        scanf("%d", &V[i]);
    }
    
    ll results[MAX_N];
    // 状态压缩：只存储必要信息
    ll *current = (ll *)malloc((N + 2) * sizeof(ll));
    ll *next = (ll *)malloc((N + 2) * sizeof(ll));
    
    // i = 1 的情况
    current[1] = K;
    results[1] = K;
    
    PirateCost *costs = (PirateCost *)malloc(N * sizeof(PirateCost));
    
    for (int i = 2; i <= N; i++) {
        int cost_cnt = 0;
        
        // 计算收买成本
        for (int j = 1; j < i; j++) {
            costs[cost_cnt].idx = j;
            costs[cost_cnt].age = j;
            if (current[j] == -1) {
                costs[cost_cnt].cost = 0;
            } else {
                costs[cost_cnt].cost = current[j] + 1;
            }
            cost_cnt++;
        }
        
        // 排序
        merge_sort(costs, 0, cost_cnt - 1);
        
        int votes_needed = V[i] - 1;
        ll total_cost = 0;
        bool feasible = true;
        
        if (votes_needed > cost_cnt) {
            feasible = false;
        } else {
            for (int j = 0; j < votes_needed; j++) {
                if (total_cost + costs[j].cost > K) {
                    feasible = false;
                    break;
                }
                total_cost += costs[j].cost;
            }
        }
        
        if (!feasible) {
            results[i] = -1;
            // 下一轮的状态：当前状态前移
            for (int j = 1; j < i; j++) {
                next[j] = current[j];
            }
            next[i] = -1;  // 当前最老海盗被扔下船
        } else {
            ll elder_coins = K - total_cost;
            results[i] = elder_coins;
            
            // 初始化下一轮状态
            for (int j = 1; j < i; j++) {
                next[j] = current[j];
            }
            
            // 被收买的海盗
            for (int j = 0; j < votes_needed; j++) {
                int idx = costs[j].idx;
                next[idx] = costs[j].cost;
            }
            
            next[i] = elder_coins;
        }
        
        // 交换current和next
        ll *temp = current;
        current = next;
        next = temp;
    }
    
    // 输出结果
    for (int i = 1; i <= N; i++) {
        printf("%lld\n", results[i]);
    }
    
    free(costs);
    free(current);
    free(next);
    
    return 0;
}

算法解释

1. 收买成本计算

对于海盗$j$（$1 \leq j \leq i-1$）：

• 如果他在$i-1$人博弈中会被扔下船（prev_coins[j] = -1），那么收买他只需要0金币
• 否则，收买他需要至少prev_coins[j] + 1金币

2. 排序策略

按收买成本升序排序，成本相同时年龄大的优先（规则4）。

3. 提案可行性

最老的海盗需要：

1. 至少有$V_i - 1$个其他海盗可收买
2. 总收买成本不超过$K$

如果任一条件不满足，提案失败，最老海盗被扔下船。

4. 状态更新

• 被收买的海盗：获得约定的金币数
• 未被收买的海盗：保持他们在$i-1$人博弈中的预期收益
• 最老的海盗：获得剩余金币

复杂度分析

• 时间：$O(N^2 \log N)$，对于$N \leq 2000$可接受
• 空间：$O(N)$

进一步优化

对于$N \leq 10^6$的大数据，需要$O(N \log N)$或$O(N)$的算法。可以使用平衡树或堆来维护可收买的海盗列表，当增加一个新海盗时，只需更新列表而无需重新排序。

// 使用最小堆优化的版本（简要思路）

typedef struct {
    ll cost;
    int age;
    int idx;
} HeapNode;

// 维护一个最小堆，堆顶是当前收买成本最低的海盗
// 每次增加一个海盗时：
// 1. 计算新海盗的收买成本
// 2. 插入堆中
// 3. 选择堆顶的V_i-1个元素

测试样例验证

对于样例1：

输入：
5
100
1
1
2
2
3
输出：
100  (i=1: 只有1个海盗)
100  (i=2: 收买第1个海盗需要0金币)
99   (i=3: 收买第1个海盗需要1金币)
99   (i=4: 收买第1,2个海盗需要1+1=2金币)
98   (i=5: 收买第1,2,3个海盗需要1+1+2=4金币)

这个算法正确地处理了所有优先级规则，并给出了符合题目要求的解。