Living-Dream 系列笔记 第23期

Problem

T1

/*
思路：
我们可以忽略两人碰到后转向的过程，直接视为两人彼此穿过了对方，
这样算距离是不变的，时间也是不变的，所以合法。
通过上述分析，
那么最小时间即为对于每一个士兵往左/右走的时间取min再取max，
最大时间反之亦然。
*/
#include<bits/stdc++.h>
using namespace std;

int l,n,a[5031];
int maxt=-1e9,mint=-1e9;

int main(){
    cin>>l>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==0){
        cout<<0<<' '<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)
        mint=max(mint,min(a[i],l+1-a[i])),
        maxt=max(maxt,max(a[i],l+1-a[i]));
    cout<<mint<<' '<<maxt;
    return 0;
}

T2

/*
思路：
因为值域很小，所以考虑采用桶排序。
每读入一个人的分数，就将其的出现次数累加1，
并算出即时的计划获奖人数，
再将分数从大到小扫描一遍，
不断累加分数出现的次数，直到>=计划获奖人数，
此时的分数即为最低分数线。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,w;
int x,mp[631];

signed main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>x,mp[x]++;
		int p=max(1ll,(int)floor(i*w/100.0)),r=0;
		for(int j=600;j>=0;j--){
			r+=mp[j];
			if(r>=p){ cout<<j<<' '; break; }
		}
	}
	return 0;
}

T3

/*
思路：
首先扫描一遍所有交头接耳的同学，
若他们同行则需要在他们中间那一列分隔，
否则需要在他们中间那一行分隔，
对于所有行按照能分隔开的同学对数排序，在对前k个按编号排序，
对列也进行如此操作即可。
*/
#include<bits/stdc++.h>
using namespace std;

int m,n,k,l,d;
struct row{
	int cnt,id;
}r[2031];
struct col{
	int cnt,id;
}c[2031];

bool cmp1(row a,row b){ return a.cnt>b.cnt; }
bool cmp2(col a,col b){ return a.cnt>b.cnt; }
bool cmp3(row a,row b){ return a.id<b.id; }
bool cmp4(col a,col b){ return a.id<b.id; }

int main(){
	cin>>m>>n>>k>>l>>d;
	for(int i=1,x,y,p,q;i<=d;i++){
		cin>>x>>y>>p>>q;
		if(y==q) 
			r[min(x,p)].cnt++,
			r[min(x,p)].id=min(x,p);
		if(x==p)
			c[min(y,q)].cnt++,
			c[min(y,q)].id=min(y,q);
	}
	
	sort(r+1,r+m+1,cmp1);
	sort(c+1,c+n+1,cmp2);
	sort(r+1,r+k+1,cmp3);
	sort(c+1,c+l+1,cmp4);
	
	for(int i=1;i<=k;i++) cout<<r[i].id<<' ';
	cout<<'\n';
	for(int i=1;i<=l;i++) cout<<c[i].id<<' ';
	return 0;
} 

T4

见题解。