admin 管理员组文章数量: 1184232
题目：
https://codeforces/contest/2126/problem/C
有n座塔，你处于第k座，每座塔高度为hi，水初始位置于1。
每秒水会上升一个单位，你拥有传送能力，可以传送至其他塔，所需为高度差的时间（秒）。
目标为在被水完全覆盖之前抵达最高塔，这是否可能。
输入每个测试由几个测试用例组成。第一行包含一个整数t(1≤t≤10^4)测试用例的数量。
每个测试用例的第一行包含两个整数n和k(1≤k≤n≤10^5)塔的数量和您最初位于的塔的索引。
第二行包含n整数h1,h2,…,hn(1≤h我≤10^9)塔楼的高度。
它保证所有的总和n在所有测试用例中，不超过10^5。
输出对于每个测试用例，如果你可以在水覆盖你之前以最大高度到达塔楼，输出一行:"YES"，或者"NO"。
解法：
这是一道贪心题，初始位于第k座塔，高度为hk，可以传到至任意塔，想要一口气传送至最高处在时间上显然是不太够的，很可能没传送就被水给淹没了。
将所有塔按高度进行排序，每次都向比当前位置下一个高的塔传送就是最优传送方案。
每次传送需要高度差的时间，同时水位也会上升这个数值的高度，只要判断水位是否超过这次传送之前的位置即可，若超过则输出“NO”。
当移动到最高处时，则输出“YES”。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int n,k,a[100001];
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
int q=a[k-1],m,water=1; //q为当前位置
sort(a,a+n); //对塔的高度排序
for(int i=0;i<n;i++){
if(a[i]>q){ //找到比当前位置高的塔进行传送
m=q; //m记录传送之前的位置
water+=a[i]-q; //水位上升高度差
q=a[i]; //移动
}
if(water>m+1){ //当水位超过传送之前的位置时，输出NO
cout<<"NO\n";
break;
}
if(q==a[n-1]){ //当“我”抵达最高处时，输出YES
cout<<"YES\n";
break;
}
}
}
return 0;
}版权声明：本文标题：cf《I Will Definitely Make It》题解 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1765515092a3388350.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论