洛谷 CSP-J2020 优秀的拆分 + 直播获奖

第一道题目：优秀的拆分：

样例以及数据范围：

?

这道题目我个人一开始是并未做出来的，因为一开始我并没有去学习位运算，然后请教了一下他人，接下来我将对这道题的思路进行解答：首先我们看到n的范围是在1的七次方之内的，所以用int 型即可，而一亿大概就对应着1左移三十位，所以我们输入n之后，先进行n是否为奇数的判断，如果是奇数，那必定没有优秀的拆分，直接输出一即可，否则n如果是偶数的话，我们不妨将偶数n想象成对应的二进制数，因为从大到小输出结果，所以我们可以考虑从30到0进行枚举，其实也可以更小，然后将1左移i位的结果与n的二进制数进行按位与操作，这样可以检查n的二进制数表示中第i位是否为1。如果为1，就需要输出2的i次方。接下来上代码：

#include<iostream>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n%2==1){
		cout<<"-1"<<endl;
		return 0;
    }
	for(int i=30;i>=0;i--){
		int ans=1<<i;
		if((n & (1<<i)) != 0){
			cout<<ans<<' ';
		}
	}
	cout<<endl;
	return 0;
}

代码很短也比较好理解，只需要掌握位运算中按位与操作符 “&”的含义即可，有兴趣的读者可以去详细了解一下位运算，接下来看第二道题目直播获奖：

?这道题我一开始的想法是读入n还有w之后，利用一个数组来存储当前评出了的所有成绩，然后从1到n进行枚举，每次枚举中先利用t计算出获奖人数，然后用sort函数对数组进行从大到小的排序，然后输出这时候数组中第t个元素就是这时候获奖的最小成绩，只不过这样的时间复杂度明显有点偏高了，首先给出我一开始65分的代码：

#include<bits/stdc++.h>
using namespace std;
int n,w;
int a[100010];
bool cmp(const int &x,const int &y){
	return x>y;
}
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	    sort(a+1,a+i+1,cmp);
		int t=max(1,(int)(i*w*0.01));
		cout<<a[t]<<' ';
	}
	return 0;
}

然后我又想了一下能不能对代码进行优化呢，当然是可以的，我考虑用插入排序，以下是代码：

#include<bits/stdc++.h>
using namespace std;
int n,w,a[110000];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i;j>=1;j--){
			if(j==1 || a[j-1]>a[j])
			break;
			swap(a[j],a[j-1]);
		}
		int k=max(1,i*w/100);
		cout<<a[k]<<' ';
	}
	cout<<endl;
	return 0;
}

欸，这时候多了二十分诶，所以这道题目使用插入排序很明显是比使用sort函数好的，但是还是没有获得满分，观察到所有人的分数都是在600以内的，所以我利用了一个数组cnt，来存储一下获得对应成绩的人的个数，在此基础上，我继续进行了优化代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,w,a[110000],cnt[610];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++){
		int k=max(1,i*w/100);
		cnt[a[i]]++;
		int s=0;
		for(int j=600;j>=0;j--){
            /*如果总共获奖的人数大于已经能够获奖的人数并且总共能够获奖的人数小于等于已经能够获奖的 
            人数加上成绩为j的人数之和，则j就为对应时刻中能够获奖的最低分数*/
			if(k>=s+1 && k<=s+cnt[j]){
		    cout<<j<<' ';
			break; 		
		}
		s+=cnt[j];
	}
	}
	cout<<endl;
	return 0;
}

?首先读入n，w还有所有的评分，然后接下来我们用for循环来从1枚举到n，对于每一次枚举，cnt数组中，下标值等于对应a数组中下标为i的加一个，也就是成绩为a[i]的人数加一，然后我们引入了一个s，这个s可以看作在每一次枚举过程中能够获奖的人数，我们插入一个从600枚举到0的循环，当寻找到能够获奖的最低分数的时候，就跳出循环，每次循环中s的初始值都是0。这段代码的核心思想就是对于每次直播打分，计算出该次打分之后能够获奖的人数k，然后先对分数为该次打分的计数器cnt加一，然后再引入s，这个s可以理解为已经确定能够获奖的人数，然后我们用一个for循环将分数从高到底进行枚举，如果在某次枚举中发现，如果k的值是大于等于已经确定能够拿奖的人数的并且看的值是小于已经可以拿奖的人数加上成绩为j的人数的，就输出这时候的j代表能够获奖的最低分数。

感谢读者的观看，如果觉得有收获的话，希望能够给我一个点赞，十分感谢！