[codeforces 1358B] Maria Breaks the Self-isolation 叫上所有伙伴 (自小到大排序+逆序处理)
Codeforces Round #645 (Div. 2) 参与排名人数14819
[codeforces 1358B] Maria Breaks the Self-isolation 叫上所有伙伴 (自小到大排序+逆序处理)
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.com/contest/1358/problem/B
| Problem | Lang | Verdict | Time | Memory |
|---|---|---|---|---|
| B - Maria Breaks the Self-isolation | GNU C++17 | Accepted | 62 ms | 800 KB |
题目看得磕磕碰碰，又是纸又是笔，对着样例写写画画，才弄明白
样例模拟如下
5
1 1 2 2 1
自小到大排序1 1 1 2 2
位置 1 2 3 4 5
数值 1 1 1 2 2
叫上所有伙伴逆序处理
位置5对应数值2,此时场地中有1+4=5>=2,1(召集人)+4(扣除位置5，剩下4人)可行，
故最终场地中有5+1(召集人)=6人6
2 3 4 5 6 7
自小到大排序2 3 4 5 6 7
位置 1 2 3 4 5 6
数值 2 3 4 5 6 7
叫上所有伙伴逆序处理
位置6对应数值7,此时场地中有1+5=6<7,1(召集人)+5(扣除位置6，剩下5人)不可行，
位置5对应数值6,此时场地中有1+4=5<6,1(召集人)+4(扣除位置5,6，剩下4人)不可行，
位置4对应数值5,此时场地中有1+3=4<5,1(召集人)+3(扣除位置4,5,6，剩下3人)不可行，
位置3对应数值4,此时场地中有1+2=3<4,1(召集人)+3(扣除位置3,4,5,6，剩下2人)不可行，
位置2对应数值3,此时场地中有1+1=2<3,1(召集人)+3(扣除位置2,3,4,5,6，剩下1人)不可行，
位置1对应数值2,此时场地中有1+0=1<3,1(召集人)+0(扣除位置1,2,3,4,5,6，剩下0人)不可行，
故最终场地中有1(召集人)=1人6
1 5 4 5 1 9
自小到大排序1 1 4 5 5 9
位置 1 2 3 4 5 6
数值 1 1 4 5 5 9
叫上所有伙伴逆序处理
位置6对应数值9,此时场地中有1+5=6<9,1(召集人)+5(扣除位置6，剩下5人)不可行，
位置5对应数值5,此时场地中有1+4=5>=5,1(召集人)+4(扣除位置5,6，剩下4人)可行，
故最终场地中有5+1(召集人)=6人5
1 2 3 5 6
自小到大排序1 2 3 5 6
位置 1 2 3 4 5
数值 1 2 3 5 6
叫上所有伙伴逆序处理
位置5对应数值6,此时场地中有1+4=5<6,1(召集人)+4(扣除位置5，剩下4人)不可行，
位置4对应数值5,此时场地中有1+3=4<5,1(召集人)+3(扣除位置4,5，剩下3人)不可行，
位置3对应数值3,此时场地中有1+2=3>=5,1(召集人)+2(扣除位置3,4,5，剩下2人)可行，
故最终场地中有3+1(召集人)=4人
AC代码如下
#include
#include
using namespace std;
int a[200010];
int main(){int t,n,i;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+1+n);//自小到大排序for(i=n;i>=1;i--)//逆序处理if(i+1>a[i])break;printf("%d\n",i+1);}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！