Educational Codeforces Round 91 (Rated for Div. 2)
题目大意：如果n个整数的序列只包含一次从1到n的所有整数，则称之为置换。
找到这样一组i，j，k，使得其满足$ 0<=i<j<k<=n$ 以及$p[i]<p[j]$ $p[j]>p[k]$
或者不存在这样的下标。存在输出“YES”换行和三个下标，不存在输出“NO”。
解题思路：因为这组数是置换，所以相邻数之间必然是递减，递增，山峰，山谷类似,遍历寻找有没有山峰就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <bits/stdc++.h>
int main(){
int t;
std::cin>>t;
while(t--){
int a[1009];
int n;
std::cin>>n;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
int flag=0;
for(int i=2;i<n;i++){
if(a[i]>a[i-1] && a[i]<a[i+1]){
std::cout<<"YES"<<"\n";
std::cout<<i-1<<" "<<i<<" "<<i+1<<"\n";
flag=1;
break;
}
}
if(!flag) std::cout<<"NO"<<"\n";
}
return 0;
}
|
题目大意：和一个机器人玩石头剪刀布，你已经知道他所出的序列，但是不知道他会从序列的哪一个开始出，你需要思考出赢场最多的策略并输出。
解题思路：由于不知道从哪里开始出，我们无法一一想出对策，贪心算序列中出现次数最多的，输出他的对应策略。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <bits/stdc++.h>
int main(){
int t;
std::cin>>t;
while(t--){
std::string a;
std::cin>>a;
int sum1=0,sum2=0,sum3=0;
for(int i=0;i<a.length();i++){
if(a[i]=='R') sum1++;
if(a[i]=='P') sum2++;
if(a[i]=='S') sum3++;
}
if(sum2>=sum1 && sum2>=sum3){
for(int i=0;i<a.length();i++){
std::cout<<'S';
}
std::cout<<"\n";
}else if(sum1>=sum2 && sum1>=sum3){
for(int i=0;i<a.length();i++){
std::cout<<'P';
}
std::cout<<"\n";
}else if(sum3>=sum1 && sum3>=sum2){
for(int i=0;i<a.length();i++){
std::cout<<'R';
}
std::cout<<"\n";
}
}
return 0;
}
|
题目大意：有n个程序员，每个程序员有对应的能力值，想要将他们组成尽可能多的队伍，每个队伍要求他们程序员的数量乘以程序员中最低能力值必须至少为x。每个程序员最多只能属于一个团队。有些程序员可能没有团队。
解题思路：将程序员的能力从大到小排序，因为较大的程序员可以自成一队，贪心思想。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <bits/stdc++.h>
bool cmp(int a,int b){
return a>b;
}
int main(){
int t;
std::cin>>t;
while(t--){
int n,x;
std::cin>>n>>x;
int a[100009];
for(int i=0;i<n;i++){
std::cin>>a[i];
}
std::sort(a,a+n,cmp);
int ans=0,sum=1;
for(int i=0;i<n;i++){
if(a[i]*sum>=x){
ans++;
sum=1;
}else{
sum++;
}
}
std::cout<<ans<<"\n";
}
return 0;
}
|