D4-1贪心

排队接水

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1005, M = N, mod = 1e9 + 7;
using namespace std;
struct node{
    int i;
    double x;
}a[N];
bool cmp(node a, node b)
{
    if(a.x == b.x) return a.i < b.i;
    else return a.x < b.x;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        double x;
        cin >> x;
        a[i] = {i, x};
    }
    sort(a + 1, a + 1 + n, cmp);
    double sum = 0, now = 0;
    for(int i = 1; i <= n; i ++)
    {
        cout << a[i].i << " ";
        now += a[i].x;
        sum += now;
    }
    cout << endl;
    printf("%.2lf", (double)sum / n);
    return 0;
}

独木舟

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1e5, M = N, mod = 1e9 + 7;
using namespace std;
int a[N];
int main()
{
    int w, n;
    cin >> w >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 1, r = n, cnt = 0;
    while(l <= r)
    {
        if(l == r)
        {
            cnt ++;
            break;
        }
        if (a[l] + a[r] > w)
        {
            r --;
            cnt ++;
        }
        else l++, r--, cnt++;
    }
    cout << cnt;
    return 0;
}

删数问题

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1005, M = N, mod = 1e9 + 7;
using namespace std;
int main()
{
    string s;
    int n;
    cin >> s >> n;
    while(n --)
    {
        bool flag = false;
        for(int i = 0; i + 1 < s.size(); i ++)
        {
            if(s[i] > s[i + 1])
            {
                s.erase(i, 1);
                flag = true;
                break;
            }
        }
        if(!flag) s.erase((int)s.size() - 1, 1);
    }
    bool flag = false;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] != '0') flag = true;
        if(flag) cout << s[i];
    }
    if(!flag) cout << 0 << endl;
    return 0;
}

最小新整数

#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1005, M = N, mod = 1e9 + 7;
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        string s;
        int n;
        cin >> s >> n;
        while(n --)
        {
            bool flag = false;
            for(int i = 0; i + 1 < s.size(); i ++)
            {
                if(s[i] > s[i + 1])
                {
                    s.erase(i, 1);
                    flag = true;
                    break;
                }
            }
            if(!flag) s.erase((int)s.size() - 1, 1);
        }
        while(s.size() > 1 && s[0] == '0')
        {
            s.erase(0, 1);
        }
        cout << s << endl;
    }
    return 0;
}

拦截导弹

//贪心
#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1e5 + 10, M = N, mod = 1e9 + 7;
using namespace std;
int n, cnt = 1, a[1005], b[1005];
int main()
{
    int x;
    while(cin >> x)
    {
        a[++ n] = x;
    }
    b[1] = a[1];
    for(int i = 2; i <= n; i ++)
    {
        int flag = false;
        for(int j = 1; j <= cnt; j ++)
        {
            if(b[j] >= a[i])
            {
                b[j] = a[i];
                flag = true;
                break;
            }
        }
        if(!flag) b[++ cnt] = a[i];
    }
    cout << cnt;
    return 0;
}

//dp
#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
typedef long long LL;
const int N = 1005, M = N, mod = 1e9 + 7;
using namespace std;
int f[N], a[N];
int main()
{
    int n = 0, ans = 0, x;
    while(cin >> x)
    {
        a[ ++ n] = x;
    }
    for(int i = 1; i <= n; i ++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j ++)
        {
            if(a[i] > a[j])
            {
                f[i] = max(f[i], f[j] + 1);
                ans = max(f[i], ans);
            }
        }
    }
    cout << ans;
    return 0;
}