专栏文章
题解:P14217 [ICPC 2024 Kunming I] 两星级竞赛
P14217题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minl6xpj
- 此快照首次捕获于
- 2025/12/02 04:13 3 个月前
- 此快照最后确认于
- 2025/12/02 04:13 3 个月前
P14217 题解
很好一道题,考验选手的细节处理能力。
题目思路
首先这道题本身并不难。我们发现,如果两项竞赛的星级不同,那么评分的关系要和星级的关系相同;而对于相同星级的竞赛,评分的关系没有特殊规定。
为了使答案尽可能优(或者是为了尽可能构造出答案),我们应该让星级较小的竞赛的评分在满足限制的情况下,尽可能达到最小,这样环环构造下去,星级最大的竞赛的评分就可能会被构造出来。
具体实现方式若有不明白,可参考代码。
题目代码
CPPint 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 条评论,欢迎与作者交流。
正在加载评论...