猫史档案馆

【CSP-J】第二题c++代码求修改

用户:发光的苦力怕查看:1 回复:5 评论:1 创建时间:2020-11-15T11:58:06

#include<bits/stdc++.h>
using namespace std;
int n,w,a[605],temp,num,sum;
int main(){
	cin>>n>>w;
	for(int i = 0;i!=n;i++){
		cin>> temp;
		a[temp]++;
		num = i+1* w/100;
		num = max(1,num);
		sum = 0;
		for(int j = 600;j>=0;j--){
			sum+=a[j];
			if(sum>= num){
				cout <<j<<" ";
				break;
			}
		}
	}
	return 0;
}

爵士OIer

第二题不是简单水题吗，用个桶或者对顶堆都行吧

爵士OIer

num = i+1* w/100;
num = max(1,num);

这里改一下

爵士OIer

因为你的num是入围人数，你把num=i+1*w/100这里1*w/100永远都是0（因为是整除），显然是不对的

爵士OIer

num = i*w/100;
num = max(1,num);

爵士OIer

而且这是动态第k小，正解应该是对顶堆吧

桶排的复杂度O(max{m,n})，这里稍作修改是O(mn)，其中m是值域。当然这里的值域是固定的，你也可以说是T(600n)，当然这么大的常数要是其他复杂度就喵了

其实BST或者Treap、Splay这种平衡树也可以做