算法入门-贪心算法

BGN29 小红的优惠券

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by XIAOBAI on 2026/5/18.
//小红的优惠券
//
// Created by XIAOBAI on 2026/5/18.
//最大 FST 距离
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
//谐距下标对
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}

void solve() {
    ll n,m;
    cin>>n>>m;
    vector<pair<int,int>> a(m);
    for(int i=0;i<m;i++) cin>>a[i].first>>a[i].second;
    sort(a.begin(),a.end(),cmp1);
    ll ans=n;
    for (int i=0;i<m;i++) {
        if (a[i].first>n) break;
        ans=min(ans,n-a[i].second);
    }
    cout<<ans;

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN30 讨厌鬼进货

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by XIAOBAI on 2026/5/18.
//讨厌鬼进货
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
//谐距下标对
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}

void solve() {
    int n,x;
    cin>>n>>x;
    vector<ll> a(n);
    vector<ll> b(n);
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    for(int i=0;i<n;i++) {
        cin>>b[i];
    }
    ll ans=0;
    for(int i=0;i<n;i++) {
        ans+=min(a[i],b[i]);
    }
    if (ans<=x) cout<<ans;
    else cout<<x;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN31 清楚姐姐买竹鼠

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
// Created by XIAOBAI on 2026/5/18.
// 清楚姐姐买竹鼠
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
//谐距下标对
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}

void solve() {
    ll a,b,x;
    cin>>a>>b>>x;
    if (a*3<=b) {
        cout<<a*x;
        return;
    }
    ll buy3=x/3;
    ll need=x%3;
    ll ans=buy3*b;
    if (a*need<b) ans+=a*need;
    else ans+=b;
    cout<<ans;

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN32 小红的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by XIAOBAI on 2026/5/19.
//小红的字符串
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}

int need(char a,char b) {
    if (b==a) return 0;
    else if (a<b) return b-a;
    else return 26-(a-b);

}
void solve() {
    string s;
    cin>>s;
    ll pos=s.size()/2;
    ll step=s.size()%2==0?1:2;
    ll ans=0;
    while (--pos>=0) {
        ans+=min(need(s[pos],s[pos+step]),need(s[pos+step],s[pos]));
        step+=2;
    }
    cout<<ans<<endl;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN33 灵异背包？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by XIAOBAI on 2026/5/19.
//灵异背包？
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}
void solve() {
    ll ans=0;
    int n;
    cin>>n;
    ll can=0;
    ll minp=1000000001;
    for(int i=0;i<n;i++) {
        ll temp;
        cin>>temp;
        ans+=temp;
        if ((temp&1)==1) {
            minp=min(minp,temp);
            can++;
        }
    }
    if (can%2==1)cout<<ans-minp;
    else cout<<ans;


}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN34 01序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by XIAOBAI on 2026/5/19.
//01序列
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<int,int> a,pair<int,int> b) {
    if (a.first!=b.first) return a.first<b.first;
    return a.second>b.second;
}
void solve() {
    ll m,n,ans=0;
    cin>>m;
    vector<ll> v(m+2,0);

    for(ll i=1;i<=m;i++) {
        cin>>v[i];
    }
    cin>>n;
    for(ll i=1;i<=m;i++) {
        if (v[i-1]==0&&v[i+1]==0&&v[i]==0) {
            ans++;
            v[i]=1;
        }

    }
    if (ans>=n) cout<<"true"<<'\n';
    else cout<<"false"<<'\n';
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

BGN35 排座椅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//
// Created by XIAOBAI on 2026/5/20.
//排座椅
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<ll,ll> a,pair<ll,ll> b) {
    if (a.second!=b.second) return a.second>b.second;
    return a.first>b.first;
}
void solve() {
    ll n,m,k,l,d;
    cin>>n>>m>>k>>l>>d;
    map<ll,ll> mpx;
    map<ll,ll> mpy;

    for (ll i=0;i<d;i++) {
        int tempx1,tempy1,tempx2,tempy2;
        cin>>tempx1>>tempy1;
        cin>>tempx2>>tempy2;
        if (tempx1==tempx2) {
            mpy[min(tempy1,tempy2)]++;
        }else {
            mpx[min(tempx1,tempx2)]++;
        }
    }
    vector<pair<ll,ll>> vx;
    vector<pair<ll,ll>> vy;
    for (const auto i:mpx) {
        if (i.second!=0) {
            auto tem=make_pair(i.first,i.second);
            vx.push_back(tem);
        }
    }
    for (const auto i:mpy) {
        if (i.second!=0) {
            auto tem=make_pair(i.first,i.second);
            vy.push_back(tem);
        }
    }
    sort(vx.begin(),vx.end(),cmp1);
    sort(vy.begin(),vy.end(),cmp1);
    vector<ll> ansx;
    vector<ll> ansy;
    for (int i=0;i<k;i++) {
        ansx.push_back(vx[i].first);
    }
    for(int i=0;i<l;i++) {
        ansy.push_back(vy[i].first);
    }
    sort(ansx.begin(),ansx.end());
    sort(ansy.begin(),ansy.end());
    for (const auto& i:ansx) {
        cout<<i<<" ";
    }
    cout<<'\n';
    for (const auto& i:ansy) {
        cout<<i<<" ";
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}


BGN36 小红的矩阵染色

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

// Created by XIAOBAI on 2026/5/20.
//小红的矩阵染色
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

bool cmp1(pair<ll,ll> a,pair<ll,ll> b) {
    if (a.second!=b.second) return a.second>b.second;
    return a.first>b.first;
}
void solve() {
    ll n,m,k;
    cin>>n>>m>>k;
    vector<vector<ll>> v(n+1,vector<ll>(m+1,-1));
    vector<ll> ans;
    for (int i=1;i<=m;i++) {v[0][i]=-1;}
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            char temp;
            cin>>temp;
            if (temp=='*') {
                v[i][j]=-1;
            }else {
                v[i][j]=0;
            }
        }
    }
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++) {
            if (v[j][i]==-1) {
                if (v[j-1][i]<=0) continue;
                else {
                    ans.push_back(v[j-1][i]);
                }
            }else {
                v[j][i]=v[j-1][i]+1;
            }
        }
        if (v[n][i]!=-1&&v[n][i]!=0) {
            ans.push_back(v[n][i]);

        }
    }

    // for (int i=1;i<=n;i++) {
    //     for (int j=1;j<=m;j++) {
    //         printf("%5lld",v[i][j]);
    //     }
    //     cout<<endl;
    // }
    sort(ans.begin(),ans.end(),cmp);
    // for (int i=0;i<ans.size();i++) {
    //     cout<<ans[i]<<" ";
    // }
    ll ans1=0;
    for (int i=0;i<ans.size();i++) {
        if (k<=0) break;
        if (k>=ans[i]+1) {
            ans1+=ans[i];
            k-=(ans[i]+1);
        }else{
            ans1+=k-1;
            break;
        }
    }
    cout<<ans1;


}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}


BGN37 小红的魔法药剂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//
// Created by XIAOBAI on 2026/5/21.
//小红的魔法药剂
#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    int n;
    cin>>n;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<pair<ll,ll>>b(n+1);
    for(int i=1;i<=n;i++) cin>>b[i].first>>b[i].second;
    ll ans=0;
    for(int i=1;i<=n;i++) {
        ans+=min(a[i],a[b[i].first]+a[b[i].second]);
    }
    cout<<ans;

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}


BGN38 交换到最大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//
// Created by XIAOBAI on 2026/5/21.
// 交换到最大

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}

int to_int(char a) {
    return a-'0';
}
char to_char(int a) {
    return a+'0';
}
void solve() {
    int t;
    cin>>t;
    while(t--) {
        string s;
        cin>>s;
        for (int i=0;i<s.size();i++) {
            int M=to_int(s[i]);
            int pos=i;
            for (int j=i+1;j<s.size()&&j-i<=10;j++) {
                if (to_int(s[j])-(j-i)>M) {
                    pos=j;
                    M=to_int(s[j])-(j-i);
                }
            }
            s[pos]=to_char(M);
            while (pos > i) {
                swap(s[pos], s[pos - 1]);
                pos--;
            }
        }
        cout<<s<<'\n';
    }

}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

/*
5891917899
7591917899
7851917899
7875

*/

BGN39 小红的整数配对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by XIAOBAI on 2026/5/21.
//小红的整数配对

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    ll n,k;
    cin>>n>>k;
     vector<ll> a(n+4,0);
    for(ll i=0;i<n;i++) {
        cin>>a[i];
    }
    ll ans=0;
    sort(a.begin(), a.end(),cmp);
    for (int i=0;i<n-1;i++) {
            if (a[i]-a[i+1]<=k) {
                ans+=a[i]*a[i+1];
                i++;
            }
    }
    cout<<ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}

/*
5891917899
7591917899
7851917899
7875

*/

BGN40 小红闯关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//
// Created by XIAOBAI on 2026/5/21.
//小红闯关

#include <iostream>
#include<unordered_map>
#include<set>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <map>
using namespace std;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
using ll = long long;
using ull = unsigned long long;
bool cmp(int a,int b) {
    return a>b;
}
void solve() {
    priority_queue<ll> q;
    ll n,k,ans=0;
    cin>>n>>k;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) {
        cin>>a[i];
    }
    for(ll i=n-1;i>=0;i--) {
        ans+=a[i];
        if (i<k-1) continue;
        if ((i+1)%k==0) {
            if (!q.empty()) {
                //cout<<q.top()<<" "<<i<<" ";
                ans-=q.top();
                q.pop();
            }
        }
        q.push(a[i]);
        //cout<<a[i]<<" "<<i<<endl;
    }
    cout<<ans;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }

}