专栏文章

题解:P14217 [ICPC 2024 Kunming I] 两星级竞赛

P14217题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minl6xpj
此快照首次捕获于
2025/12/02 04:13
3 个月前
此快照最后确认于
2025/12/02 04:13
3 个月前
查看原文

P14217 题解

很好一道题,考验选手的细节处理能力。

题目思路

首先这道题本身并不难。我们发现,如果两项竞赛的星级不同,那么评分的关系要和星级的关系相同;而对于相同星级的竞赛,评分的关系没有特殊规定。
为了使答案尽可能优(或者是为了尽可能构造出答案),我们应该让星级较小的竞赛的评分在满足限制的情况下,尽可能达到最小,这样环环构造下去,星级最大的竞赛的评分就可能会被构造出来。
具体实现方式若有不明白,可参考代码。

题目代码

CPP
int t;
vector < long long > v[400005];
pair < long long , int > s[400005]; // 只对 pair 排序,用 second 位置存的对应下标访问 vector
void solve()
{
    long long n , m , k;
    read(n , m , k);
    for(int i = 1 ; i <= n ; i++)
    {
        v[i].clear(); // 注意清空
        read(s[i].first);
        s[i].second = i;
        v[i].push_back(0); // 提前塞一个元素让下标从 1 开始,便于写代码
        for(int j = 1 ; j <= m ; j++)
        {
            long long x;
            read(x);
            v[i].push_back(x);
        }
    }
    sort(s + 1 , s + n + 1);
    long long maxx = 0; // 全局 max
    long long lst = 0; // 上一个星级
    long long lstmaxx = 0; // 不包括当前星级的 max
    for(int p = 1 ; p <= n ; p++)
    {
        int i = s[p].second; // 当前 s[p] 对应的 vector 下标是 i
        long long minget = 0 , maxget = 0; // 当前比赛可以得到的最小评分 / 最大评分
        for(int j = 1 ; j <= m ; j++)
        {
            minget += (v[i][j] == -1 ? 0 : v[i][j]);
            maxget += (v[i][j] == -1 ? k : v[i][j]);
        }
        if(lstmaxx <= maxget) // 后文更新全局最大值时会 + 1,所以这里可以取等
        {
            long long minuse = max(minget , lstmaxx);
            maxx = max(maxx , minuse); // 更新全局 max
            long long more = minuse - minget; // 多出来的部分,要在 -1 位置修改
            for(int j = 1 ; j <= m ; j++)
            {
                if(v[i][j] == -1)
                {
                    if(more)
                    {
                        v[i][j] = min(more , k);
                        more -= min(more , k);
                    }
                    else
                    {
                        v[i][j] = 0;
                    }
                }
            }
        }
        else
        {
            printnl("No");
            return ;
        }
        if(s[p + 1].first > s[p].first) // 此时下一个星级发生变化,需要更新
        {
            maxx++; // 注意不同星级之间评分是不相等的,此处对应前文可以取等的原因
            lst = s[p].first;
            lstmaxx = maxx;
        }
    }
    printnl("Yes");
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            printsp(v[i][j]);
        }
        print("\n");
    }
}
signed main()
{
    read(t);
    while(t--)
    {
        solve();
    }
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...