csoj练习题目第一天。

新年礼物

签到题，直接模拟过程即可。

#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
int n;
int price[MAX],beauty[MAX];
//vector<int> p(n),w(n);

int func(int step,int counts,int now_beauty,int now_price)
{
	while(step!=n){
		if(now_beauty<beauty[step+1])
		{
			if(price[step+1]<now_price) counts++;
			now_price=price[step+1];
			now_beauty=beauty[step+1];
		}
		step++;
	}
	return counts;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>beauty[i];
	for(int i=1;i<=n;i++) cin>>price[i];
	cout<<func(0,0,0,0);
	return 0;
}

灯笼展

这题我的第一思路是走一步排序并找第k小，感觉慢了，后来发现只需要保证前k小即保证了第k个一定是最小的，也就是说，这个题需要每走一步维护一次前k小的数。

代码：

#include <bits/stdc++.h>
#define MAX 100005
using namespace std;
int n,k;
priority_queue<int> q;


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	vector<int> a(n);//一定要在输入n之后再定义
	for(auto& x : a) cin>>x;
	
	for(auto &x:a)
	{
		if(q.size()<k||q.top()>x) cout<<"-1"<<endl;
		else cout<<q.top()<<endl;
		q.push(x);
		if(q.size()>k) q.pop();
	}

	return 0;
}

这个代码有几点注意的地方，首先是容器vector和priority_queue()。使用vector代替数组时要注意先输入n再定义vector，否则会出现经典的segment fault！！！然后priority_queue()是一个可以自己排序的一个队列，push元素进入时会自动排序并使最顶的元素为最大值，即从小到大排序，这样每走一次将该元素入队，自动排序后判断队列长度和k的大小关系，使该队列数字保持在k个且是前k小，之后每次达成条件输入队顶数字即可。