贪心

· · 个人记录

贪心

练习

B3959 [GESP202403 四级] 做题

做题之前先来看看时间复杂度。n<=10^6在这种情况下如果我们去直接枚举的话绝对拿不到满分，那么我们只能另寻他路。
首先这道-题说的是第一天要做i道题目那么如果那么我们就可以想想看。
假设有1~10道题库那么如果你第一天就做10那么到最后第10天时你就毫无办法了。
所以我们再选择这天因该做多少题时因该选则的是第一给大于等于当前天数的。
你要知道我们要小对小，大对大这样才能再对方出大时可以打过最后只要看能满足多少天就可以了

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[10000005];
int cnt,u = 1;
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    sort(a + 1 , a + 1 + n);
    for(int i = 1 ; i <= n ; i ++){

        while(a[u] < i && u <= n)u ++;
        if(u > n)break;
        u ++;
        cnt ++;
        if(u > n)break;
    }
    cout << cnt;
    return 0;
}

P2813 母舰

思路

按照往常不管三七二十一先来看看范围n <= 10^5如果去枚举的话拿不到分的所以又得另寻他路。
一样的想要攻击道母舰的伤害尽可能高那么我们再击溃母舰的防御系统时就不能盲目的用自己的系统根母鸡那对打。
首先想要在打破母舰的系统的情况下剩余的伤害更高那么我们就必须再打防御系统时自己的攻击要再大于了防御系统的情况下尽可能小
所以一切都十分简单了我们使用二分找到第一个大于等于的攻击系统。（注意，用过的不能再用要打标记也就是排除再选到同一搜）

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],b[1000005],pos = 1,sum;
int main(){
    cin >> m >> n;
    if(m >= n){
        cout << 0;
        return 0;
    }
    for(int i = 1 ; i <= m ; i ++){
        cin >> b[i];
    }
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    sort(a + 1 , a + 1 + n);
    sort(b + 1 , b + 1 + m);
    for(int i = 1 ; i <= m ; i ++){
        pos = lower_bound(a + pos , a + 1 + n , b[i] + 1) - a;
        if(pos > n){
            cout << 0;
            return 0;
        }
        a[pos] = 0;
        pos ++;
    }
    for(int i = 1 ; i <= n ; i ++){
        sum += a[i];
    }
    cout << sum;
    return 0;
}

P1167 刷题

思路

这题看似好像是贪心但是我认为这道题主要的并不是贪心这道题目的主要就是求出这段时间内有多少天。
首先如果你为了保险一天一天的算那么我们就来计算一下时间10000 * 365 * 24 * 60 = 5256000000在时间上来不及。
那么我们就可一个月一个月的算这样时间复杂度就是10000 * 12 = 120000的时间复杂度不会超。
所以我们可以一个月的求出了多少分钟后再小小的贪一下因为要最小那么肯定优先选最小啊。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[5005];
int mon[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int year1,m1,d1,h1,f1;
int year2,m2,d2,h2,f2;
bool isrun(int x){
    if(x % 4 == 0 && x % 100 != 0 || x % 400 == 0){
        return true;
    }
    return false;
}
int check(int x){
    if(isrun(x)){
        return 366;
    }
    return 365;
}
int GET(){
    int sum = 0,sum1 = 0,sum2 = 0;
    sum1 = (d1 - 1) * 24 * 60 + h1 * 60 + f1;
    for(int i = 0 ; i < year1 ; i ++){
        sum1 += check(i) * 24 * 60;
    }
    if(check(year1) == 366){
        mon[2] = 29;
    }else{
        mon[2] = 28;
    }
    for(int i = 1 ; i < m1 ; i ++){
        sum1 += mon[i] * 24 * 60;
    }
    sum2 = (d2 - 1) * 24 * 60 + h2 * 60 + f2;
    for(int i = 0 ; i < year2 ; i ++){
        sum2 += check(i) * 24 * 60;
    }
    if(check(year2) == 366){
        mon[2] = 29;
    }else{
        mon[2] = 28;
    }
    for(int i = 1 ; i < m2 ; i ++){
        sum2 += mon[i] * 24 * 60;
    }
    sum = sum2 - sum1;
    return sum;
}
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    sort(a + 1 , a + 1 + n);
    char c;
    cin >> year1 >> c >> m1 >> c >> d1 >> c >> h1 >> c >> f1;
    cin >> year2 >> c >> m2 >> c >> d2 >> c >> h2 >> c >> f2;
    int res = GET();
    int cnt = 0;
    for(int i = 1 ; i <= n ; i ++){
        if(res >= a[i]){
            res -= a[i];
            cnt ++;
        }else{
            break;
        }
    }
    cout << cnt;
    return 0;
}

B3928 [GESP202312 四级] 田忌赛马

思路

哈哈一场新的田忌赛马首先判断我们能赢多少次，能不能去枚举呢？
不能，因为n <= 3 * 10^5所以我们就要想个合适的办法了。
首先我们来思考一个问题，假设田忌的马的速度是从小到大排序的那么如果第i个我们都斗不过了那么后面的呢？绝对也斗不过了。
所以对于第i匹马我们因该找出第一匹比田忌这匹马的脚力要大的马这样再既可以打败田忌又可以为后面的马增加胜算，最后看看能打败多少匹就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[50005],b[50005];
int main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    for(int i = 1 ; i <= n ; i ++){
        cin >> b[i];
    }
    sort(a + 1 , a + 1 + n);
    sort(b + 1 , b + 1 + n);
    int u = 1,ans = 0;
    for(int i = 1 ; i <= n ; i ++){
        while(a[u] < b[i] && u <= n){
            u ++;
        }
        u ++;
        ans ++;
        if(u > n)break;

    }
    cout << ans;
    return 0;
}

作业

P1173 [NOI2016] 网格
P1915 [NOI2010] 成长快乐
P2565 [SCOI2009] 骰子的学问
P2703 [NOI2006] 千年虫