1041A - Heist #include<cstdio>#include<algorithm>using namespace std;int a[1005];int main(){ in
... .
1041A - Heist
.#include<cstdio>#include<algorithm>using namespace std;int a[1005];int main(){ int n,ans=0; scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<n;++i) ans+=a[i+1]-a[i]-1; printf("%d",ans); return 0;}.
1041B - Buying a TV Set
.#include<cstdio>typedef long long ll;ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}int main(){ ll a,b,x,y,t; scanf("%lld%lld%lld%lld",&a,&b,&x,&y); t=gcd(x,y); x/=t; y/=t; double c1=(double)a/x,c2=(double)b/y; x=c1+1e-7,y=c2+1e-7; if(y<x) x=y; printf("%lld",x); return 0;}.
1041C - Coffee Break
题目大意：
某人每天工作时间m分钟，在a1,a2,...,an分钟 他可以休息，但是同一天任意两次休息必须间隔至少d分钟。问他至少需要多少天才能在每个可休息时间点都至少休息一次（就是说对于任意ai,总有一天在第ai分钟休息了）
解题思路：
a数组首先要排序
1.平衡树treap
首先把n个时间都放入treap中
第1天我们找出平衡树中最为靠前的那个，即a1，删除a1,然后在treap中找到a1+d的后继a‘，删除a‘,然后再找a‘+d的后继...直到找不到，说明第一天结束。
然后第二天继续这样的操作，直到treap为空。
时间复杂度： 至少进行n次查找，treap中操作复杂度logn 所以为O(nlogn)
2.一个类似于队列的思想
ts[i]表示第i分钟在第ts[i]天休息了。
ans表示总共的天数，初值为1
设一个数组q，开始a1入队，ts[1]=1
然后从a2开始循环 i=2...n
对于ai如果它可以和q[t]同一天休息那么就++t，ts[i]=ts[q[t]];
否则q[t]=++ans;
最后q[++w]=i;
意思是q[t]一定是可接尾里时间最靠前的那个
.#include<cstdio>#include<algorithm>using namespace std;const int N=2e5+5;struct X{ int a,id; bool operator<(const X &b){ return a<b.a; }}x[N];int ts[N],q[N];int rd(){ char c; while((c=getchar())<‘0‘||c>‘9‘); int re=c-‘0‘; while((c=getchar())>=‘0‘&&c<=‘9‘) re=(re<<1)+(re<<3)+c-‘0‘; return re; }int main(){ int n=rd(),t=1,m=rd(),d=rd(),w=1,ans=1; for(int i=1;i<=n;++i) x[x[i].id=i].a=rd(); sort(x+1,x+n+1); ts[x[1].id]=q[1]=1; for(int j=2;j<=n;++j){ if(x[j].a-x[q[t]].a-1>=d) ts[x[j].id]=ts[x[q[t]].id],++t; else ts[x[j].id]=++ans; q[++w]=j; } printf("%d/n",ans); for(int i=1;i<=n;++i) printf("%d ",ts[i]); return 0;}. . .. ...
