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

简介: 算法

战绩战绩

14.png

被爆*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


题意:

15.png

思路:

简化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的数字
      //反着找就是加个greater
      if(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;
}
相关文章
|
27天前
|
人工智能 测试技术 BI
Codeforces Round 942 (Div. 2)
Codeforces Round 942 (Div. 2)
|
27天前
|
人工智能 测试技术 芯片
Codeforces Round 963 (Div. 2)
Codeforces Round 963 (Div. 2)
|
4月前
Codeforces Round #567 (Div. 2)
【7月更文挑战第1天】
45 7
|
5月前
Codeforces Round #729 (Div. 2)
【6月更文挑战第4天】在这两个编程问题中,B. Plus and Multiply 要求判断通过加法和乘法操作数组是否能形成目标数 `n`。思路是形如 `x^a + yb = n` 的表达式,如果满足则能构造。C. Strange Function 关注的是找到最小正整数 `x` 使得 `x` 不是 `i` 的因子,计算这些值的和模 `10^9+7`。对于每个 `i`,偶数时 `f(i)` 是 3,奇数时是 2,利用因子与最大公约数计算周期性求和。
30 1
Codeforces Round #178 (Div. 2)
在n条电线上有不同数量的鸟, Shaass开了m枪,每一枪打的是第xi条电线上的第yi只鸟,然后被打中的这只鸟左边的飞到第i-1条电线上,右边的飞到i+1条电线上,没有落脚点的鸟会飞走。
50 0
|
机器学习/深度学习 Go
codeforces round 885 (div. 2)
codeforces round 885 (div. 2)
95 0