Codeforces Round #509 (Div. 2)(暑假训练8.14)(A-C)

本文主要是介绍Codeforces Round #509 (Div. 2)(暑假训练8.14)(A-C)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

战绩战绩

被爆*N,这个C确实没想明白，兴哥永远滴cs！！

A. Heist

题意：
有许多的键盘，这些键盘的编号连续，但是某些键盘被偷了，现在给你剩下的键盘的编号，求被偷的键盘数量的最小值。
思路：
由于键盘编号连续，那么最少的键盘数量就一定是最大的键盘编号减去最小的键盘编号再加一。

#include<bits/stdc++.h>
using namespace std;
int main()
{int d,n,max1=inf,min1=0;cin>>n;for(int i=0;i<n;i++){cin>>d;max1=min(max1,d);min1=max(min1,d);}cout<<(min1-max1)-n+1<<endl;
}

B. Buying a TV Set

题意：

思路:
简化x/y，那么就都除以他们的gcd啦，简简单单~

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{int a,b,x,y;cin>>a>>b>>x>>y;int d1=__gcd(x,y);x/=d1,y/=d1;cout<<min(a/x,b/y)<<endl;
}

C. Coffee Break

题意：
给定n个数和一个k，这n个数都不超过m，每次从没被去掉的数里面选一个数a，去掉a，然后可以任意一个b(b>a+k)，然后去掉任意一个c(c>b+k)，以此类推，问最少能选多少个a，然后输出每个数都是选第几个a的时候被去掉的
思路：
这题需要利用set和pair了，还需要用到二分查找的函数upper_bound，对于每一天都去贪心的从小找到大，看比当前时间+k小的时间点能不能被找到，被找到就继续找，找不到就换下一天，兴哥是优先队列搞的
贴贴代码，是个好题!!

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int a[MAX],ans[MAX];
set<pair<int,int> > ss;
set<pair<int,int> > :: iterator it;
int n,m,d,cnt;
int main()
{cin>>n>>m>>d;for(int i = 1; i<=n; i++) {scanf("%d",a+i);ss.insert(make_pair(a[i],i));       //set的默认比较规则是按照first比较 ，first相同再按照second比较}while(!ss.empty()) {int pos = ss.begin() -> second;ans[pos] = ++cnt;ss.erase(ss.begin());while(1) {it = ss.upper_bound(make_pair(a[pos]+d,INF));//inf因为是在set里调用upper_bound函数所以要的时候万一有一个等于num的会因为second的大小跳出//upper_bound查找第一个大于num的数字//lower_bound查找第一个大于等于的num的数字//反着找就是加个greaterif(it == ss.end()) break;//没找到就及时跳出去pos = it->second;ans[pos] = cnt;ss.erase(it);}}printf("%d\n",cnt);for(int i = 1; i<=n; i++) printf("%d%c",ans[i],i==n ? '\n' : ' ');return 0;
}

这篇关于Codeforces Round #509 (Div. 2)(暑假训练8.14)(A-C)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---