Living-Dream 系列笔记 第20期

Problem

T1

/*
思路：
统计每个人成绩的出现人次，
然后贪心地按分数值域从大到小扫描一遍，
每次令答案累加上当前分数出现的人次，
若答案>=k就停止扫描并输出即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k,a[2031];
int cnt,ans;
int mp[131];

signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
    for(int i=120;i>=0&&ans<k;i--) 
        ans+=mp[i];
    cout<<ans;
    return 0;
}

T2

/*
思路：
二分最大边长，对于猜到的mid，遍历n块巧克力，计算能分成的块数，与k比较即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k;
int maxh=-1e9,maxw=-1e9;
int h[100031],w[100031];

bool check(int x){
    int res=0;
    for(int i=1;i<=n;i++) res+=(h[i]/x)*(w[i]/x);
    return res>=k;
}

signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) 
		cin>>h[i]>>w[i],maxh=max(maxh,h[i]),maxw=max(maxw,w[i]);
	int l=-1,r=min(maxh,maxw)+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	cout<<l;
	return 0;
}

T3

/*
思路：
二分要买的冰棍数，对于猜到的mid，模拟买冰棍的过程并计算能吃到的冰棍数，与n比较即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;

bool check(int x){
	int sum=x,mg=x,bg=0;
	while(1){ 
		mg+=bg;
		if(mg<3) break;
		sum+=mg/3,bg=mg/3,mg%=3;
	}
	return sum>=n;
}

signed main(){
	cin>>n;
	//cout<<check(14);
	int l=0,r=n+1;
	while(l+1<r){
		//cout<<l<<' '<<r<<'\n';
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}

T4

/*
思路：
题目实际上是让我们在一个n*n的矩阵中找最小的n个数，如下表：
a[1]+b[1] a[1]+b[2] a[1]+b[3] ... a[1]+b[n]
a[2]+b[1] a[2]+b[2] a[2]+b[3] ... a[2]+b[n]
...       ...       ...       ... ...
a[n]+b[1] a[n]+b[2] a[n]+b[3] ... a[n]+b[n]
于是我们想到建立一个优先队列，维护最小的n个数，初始值为第一行的数。
对于矩阵中的每一个不是第一行的数a[i]+b[j]，
考虑将其替换优先队列中的最大值：
若a[i]+b[j]>=优先队列的队首，则直接剔除队首，并且跳过这一行的所有数；
（为什么可以这样做呢？
因为矩阵中的每一个行/列都是单调不降的，
若a[i]+b[j]>=优先队列的队首，
则这一行在它后面的元素都一定>=优先队列的队首，
所以无需考虑后面的。）
否则，剔除队首，并且加入a[i]+b[j]。
最后用一个栈倒序存储优先队列的元素，并输出即可。

时间复杂度分析：
第一行的进队次数为n；
第二行的a[2][n/2]的元素有a[2][1~n/2]这n/2个元素<=它，
且有a[1][1~n/2]这n/2个元素也<=它，共n个元素；
此时它应当是优先队列的队首，
而a[2][n/2+1]一定>=它，于是后面的都会被排除，
因此第二行的进队次数至多为n/2；
同理第三行的进队次数至多为n/3；
于是我们得到了：第i行的进队次数至多为n/i，
因此n行的进队次数总和至多为n+n/2+n/3+...+1，
俗称调和级数，大约为O(logn)。
而优先队列的每次操作均为O(logn)，
所以总的时间复杂度为O(n(logn)^2)。
*/
#include<bits/stdc++.h>
using namespace std;

int n,a[100031],b[100031];
priority_queue<int> pq; //优先队列
stack<int> stk; //用于倒序的栈

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            int x=a[i]+b[j]; //取出当前元素
            if(pq.size()<=n) pq.push(x); //大小不够n直接加入
            else{
                if(x>=pq.top()){ pq.pop(); break; } //>=队首的直接剔除队首并跳过当前行
                else pq.pop(),pq.push(x); //否则剔除队首并将当前元素加入优先队列
            }
        }
    while(!pq.empty()) stk.push(pq.top()),pq.pop(); //倒序
    while(!stk.empty()) cout<<stk.top()<<' ',stk.pop();
    return 0;
}