题解：P17297 [ICPC 2026 Xi'an I] Qenerals

York1121 · 2026-08-27 09:36:40 · 题解

Description

• 初始 Yuki 有 1 个堡垒和 0 个士兵。
• Yuki 可以选择消耗 a_j 个士兵占领一个堡垒，并获得每秒多生产一个士兵的能力。当然 Yuki 也可以选择不操作。

思路

这是一个经典的贪心算法问题。

我们先将所有的 a_i 按升序排序，并依次占领编号 1,2, \dots ,n 的最小的堡垒。对于每个堡垒，计算需要等待多少秒才能积攒足够的士兵来占领它。如果在某一步，所需时间超过了总时间 m，则停止尝试更多的堡垒。在每一步成功占领后，计算如果此时停止扩张，剩余时间全部用于生产所能得到的最终士兵数，并更新全局最大值。

AC Code

#include <bits/stdc++.h>
using namespace std;
int n,m,t;
int a[3374982];
void solve() 
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) 
        {
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        long long cur_x=0;      
        long long cur_y=1;      
        long long cur_t=0;      
        long long ans=m;    
        for(int i=1;i<=n;i++) 
        {
            long long cost=a[i];
            long long wait=0;
            if(cur_x<cost) 
            {
                long long diff=cost-cur_x;
                wait=(diff+cur_y-1)/cur_y;
            }
            long long next_t=cur_t+wait;
            if(next_t>m) 
            {
                 break;
            }
            cur_x+=wait*cur_y;
            cur_x-=cost;
            cur_y+=1;
            cur_t=next_t;
            long long time=m-cur_t;
            long long final_x=cur_x+time*cur_y;
            if(final_x>ans) 
            {
                ans=final_x;
            }
    }
        cout<<ans<<endl;
    } 
}
int main() 
{   
    solve();
    return 0;
}