Codeforces Round#509 (Div. 2)

比赛传送门

​

A. Heist

排个序直接得到结果

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=1005;
int n,a[maxn],ans;
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for (int i=1;i<n;i++) ans+=a[i+1]-a[i]-1;
	printf("%d",ans);
	return 0;
}

B. Buying a TV Set

\(Min\{\lfloor \frac a x \rfloor,\lfloor \frac b y \rfloor \}\)

注意\(x,y\)不互质的情况

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll gcd(ll x,ll y) {return y==0?x:gcd(y,x%y);}
int main(){
	ll a,b,x,y;
	scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
	ll t=gcd(x,y);x/=t;y/=t;
	printf("%lld",min(a/x,b/y));
	return 0;
}

C. Coffee Break

贪心，能往时间线上排就放上去

multiset真好用

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;

const int maxn=200005;
int n,m,d,a[maxn],when[maxn];
struct data{
	int x,id;
	data () {}
	data (int _x,int _id):x(_x),id(_id) {}
	bool operator<(const data&b)const {return x<b.x;}
};
multiset<data> S;
typedef multiset<data>::iterator iter;
int main(){
	scanf("%d%d%d",&n,&m,&d);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),S.insert(data(a[i],i));
	int ans=0;
	while (S.size()){
		int nxt=1;ans++;
		while (1){
			iter it=S.lower_bound(data(nxt,0));
			if (it==S.end()) break;;
			when[(*it).id]=ans;
			nxt=(*it).x+d+1;S.erase(it);
		}
	}
	printf("%d\n",ans);
	for (int i=1;i<=n;i++) printf("%d ",when[i]);
	return 0;
}

D. Glider

看这里

E. Tree Reconstruction

看这里

F. Ray in the tube

看这里