【结论题】CF1238B Kill ‘Em All

小咪咪 2024-03-16 11:42 51阅读 0赞

**来写点简单题题解放松一下**

题意：

![d9e0bfcefb5143c79ec8ff7f56b33140.png][]

![8476e33b8e0a4c928e9d09ccc4d0e7b1.png][]

思路：

首先观察样例可以猜想几个结论：

1.导弹的位置一定是和存活的xi重合的

这点好证明，如果不重合，左边的-r，右边的不影响，重合的至少还用炮炸死了一个，一定不差

2.每次选最右边的还存活的xi炸

肯定是吧，感觉都不需要证明，和上面那个同理

3.有没有炸完只需看每次炸的位置左边那个位置即可

想一想，好像确实是这样

因此可以直接维护炸的次数，枚举一遍就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    vector<int> v;
    set<int> S;
    
    int N,r;
    int a[mxn];
    
    void solve(){
        S.clear();
        v.clear();
        cin>>N>>r;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            S.insert(a[i]);
        }
        for(auto it:S) v.push_back(it);
        sort(v.begin(),v.end());
        int x=0;
        for(int p=v.size()-1;p>=1;p--){
            x++;
            if(x*r>=v[p-1]){
                cout<<x<<'\n';
                return;
            }
        }
        x++;
        cout<<x<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[d9e0bfcefb5143c79ec8ff7f56b33140.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cd423c22360849fdb1d7676aab3fb570.png
[8476e33b8e0a4c928e9d09ccc4d0e7b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3aac29bd700f443fa68092331f6cd849.png

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 111 阅读

相关 CF1200B

CF1200B 解法： > 贪心。当在第i列时，尽可能多的取走第i列的木块使得袋子里的木块尽可能多 CODE: include<iostre...

本是古典何须时尚/ 2024年04月20日 10:29/ 0 赞/ 94 阅读

相关 CF1207B

CF1207B-Square Filling 题意： > 两个矩阵a,b，已知矩阵b，每次能修改b矩阵中相邻的四个格（b为空矩阵），使b变为a 解法： ...

梦里梦外;/ 2024年04月20日 10:28/ 0 赞/ 101 阅读

相关 CF1195B

CF1195B 题意： > 有一个盒子，每次可以做两个操作： > > > 1.每次吃掉一块蛋糕 > > 2.每次放入比上一次放入数多1的蛋糕 > ...

墨蓝/ 2024年04月20日 10:28/ 0 赞/ 100 阅读

相关 CF1208B

CF1208B 题意： > 给出n个数字，找出最小的一端连续区间进行删除操作，使其剩余元素不含重复元素，求要删除的最小区间长度解法： > 删除子段...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:28/ 0 赞/ 94 阅读

相关【反悔贪心】CF1278B CF11B

[Problem - 1278B - Codeforces][] 题意： ![c0fbd2f3d4224469b8dd5bb7d049f4ee.png][] 思路： !

以你之姓@/ 2024年03月24日 18:30/ 0 赞/ 106 阅读

相关【结论题】CF1238B Kill ‘Em All

来写点简单题题解放松一下题意： ![d9e0bfcefb5143c79ec8ff7f56b33140.png][] ![8476e33b8e0a4c928e9d09cc

小咪咪/ 2024年03月16日 11:42/ 0 赞/ 52 阅读

相关【结论+贡献+枚举+排列】CF1671D

[Problem - D - Codeforces][] 题意： ![6d38d81dece9480b806df1bb2b77a575.png][] 思路：结论是一步

深藏阁楼爱情的钟/ 2024年03月16日 10:43/ 0 赞/ 37 阅读

相关 D. AB-string——CF1238D

https://codeforces.com/problemset/problem/1238/D 思路： 1、每个字符存在回文串的最地条件是： AA ， BB， ABA

小灰灰/ 2023年06月06日 10:35/ 0 赞/ 41 阅读

相关 CF1174B Ehab Is an Odd Person(排序+结论)

做法一个显然的结论就是如果至少有一个奇数和一个偶数，那么是可以随意调整的，也就是升序排序否则不可以进行任何操作 Code include<bits/

浅浅的花香味﹌/ 2021年12月03日 04:47/ 0 赞/ 197 阅读