A. Heist
题意:找出最大数和最小数之前缺少了多少个数
题解:排序之后直接计算
#include <bits/stdc++.h>
const int MAXN = 10000;
using namespace std;
int N,sum;
int a[MAXN];
int main()
{
scanf("%d",&N);
for(int i = 1;i <= N;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+N+1);
sum = a[N] - a[1] - N + 1;
printf("%d\n",sum);
return 0;
}
B. Buying a TV Set
题意:电视的尺寸比例是xy的,问你在ab的墙上可以挂多少种不同尺寸的电视
题解:先化简x/y,然后分别用长和宽去处于a和b取较小的值
#include <bits/stdc++.h>
using namespace std;
long long a,b,x,y,gc;
long long c,d;
int main()
{
scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
gc = __gcd(x,y);
x /= gc;y /= gc;
c = a / x;
d = b / y;
printf("%lld\n",min(c,d));
return 0;
}
C. Coffee Break
有n个休息时刻,你需要把这n个休息时刻安排到尽量少的天中,使得每两个休息时刻的间隔大于d分钟,一天有m分钟。注意两天之间的间隔大于d分钟
题解:用set对时间排序,然后先取出一个时间然后取出大于d的时间,如果不存在就天数++
#include <bits/stdc++.h>
const int MAXN = 200005;
using namespace std;
int N,M,D,sum;
int Day[MAXN];
struct node{
int val,id;
friend bool operator < (const node &A,const node &B){
return A.val < B.val;
}
};
set<node>S;
set<node>::iterator it;
inline int read()
{
int x = 0;char ch = getchar();
while(ch < '0' || '9' < ch){ch = getchar();}
while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
return x;
}
int main()
{
N = read();M = read();D = read();
int v;
for(int i = 1;i <= N;i++){
v = read();
S.insert((node){v,i});
}
for(sum = 1;!S.empty();sum++){
it = S.begin();
Day[(*it).id] = sum;
v = (*it).val;
S.erase(it);
while(1){
it = S.upper_bound((node){v+D,0});
if(it == S.end()) break;
Day[(*it).id] = sum;
v = (*it).val;
S.erase(it);
}
}
printf("%d\n",sum-1);
for(int i = 1;i <= N;i++) printf("%d ",Day[i]);
return 0;
}
D. Glider
题意:你从H的高度往下落,下降的过程中存在N个平流层在平流层飞行高度不会变化(只会向X的正半轴平移而不会向Y轴负半轴平移),如果不在平流层,则每次向X正半轴位移的同时,会向Y的负半轴平移
题解:计算从第一个平流层起点起飞,最远能到哪儿,然后计算到下个平流层需要起点往后多远
#include <bits/stdc++.h>
const int MAXN = 200005;
using namespace std;
int N,H,sum,ans,ql;
struct node{
int L,R;
}C[MAXN];
inline int read()
{
int x = 0;char ch = getchar();
while(ch < '0' || '9' < ch){ch = getchar();}
while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
return x;
}
inline void init(){
N = read();H = read();
for(int i = 1;i <= N;i++){
C[i].L = read();C[i].R = read();
}
ql = 1;sum = C[1].R - C[1].L;
for(int i = 2;i <= N;i++)
{
if(H > C[i].L - C[i-1].R){
H -= C[i].L - C[i-1].R;
sum += C[i].L - C[i-1].R;
sum += C[i].R - C[i].L;
ans = max(ans,sum+H);
continue;
}
while(H < C[i].L - C[i-1].R + 1){
if(ql == i) continue;
H += C[ql+1].L - C[ql].R;
sum -= C[ql+1].L - C[ql].R;
sum -= C[ql].R - C[ql].L;
ql++;
}
H -= C[i].L - C[i-1].R;
sum += C[i].L - C[i-1].R;
sum += C[i].R - C[i].L;
ans = max(ans,sum+H);
}
if(N == 1) ans = C[1].R - C[1].L + H;
}
int main(){
init();
printf("%d",ans);
return 0;
}