崇礼夏令营日记之7月22的贪心算法之旅
2025-07-22 15:22:55
发布于：河北
2阅读
0回复
0点赞
我终于能上小码王的夏令营啦！！！
不过题还是挺简单的，毕竟是入门算法的红题为主，一部分是橙题。
今天讲了一大堆干货呀，如果有人想看那就看看八（全是题目）！
1.字典序排序
这里有重排字符串这道题
其实，字典序就是从高位一位一位往下比，一旦遇到字符更大就比出来了
#include<bits/stdc++.h>
using namespace std;
int main (){
int n;
cin >> n;
string s="";
string t="";
while (n--){
cin >> s;
cin >> t;
sort (s.begin(), s.end());
sort (t.begin(), t.end());
reverse (t.begin(), t.end());
if (s < t)
cout << "YES\n";
else
cout <<"NO\n";
}
return 0;
}
2.贪心考虑最终状态的应用
这题：吃最少的食物
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[1000000],b[1000000];
signed main(){
int n,sweaty,salty;
cin>>n>>sweaty>>salty;
for (int i = 0; i < n; i++){
cin >>a[i];
}
for (int i = 0; i < n; i++){
cin >>b[i];
}
sort(a,a+n,greater<int>());
sort(b,b+n,greater<int>());
int sum1 = 0;
int sum2 = 0;
int ans1=0;
int ans2=0;
for (int i = 0; i < n; i++){
sum1 += a[i];
ans1++;
if (sum1 > sweaty){
break;
}
}
for (int i = 0; i < n; i++){
sum2 += b[i]; ans2++;
if (sum2 > salty){
break;
}
}
cout <<min(ans1,ans2);
return 0;
}
3.贪心数学优化
这两题：三个数的最大乘积
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum = 0;
signed main(){
int n ;
cin>>n;
int t = n / 10;
int k = n % 10;
if (k >= 7)t++;
else sum += k * 15;
sum += t * 100;
cout <<sum;
return 0;
}
还有章鱼烧の最少花费
其中，章鱼烧の最少花费比较简单
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sum = 0;
signed main(){
int n ;
cin>>n;
int t = n / 10;
int k = n % 10;
if (k >= 7)t++;
else sum += k * 15;
sum += t * 100;
cout <<sum;
return 0;
}
4.贪心从小问题推到大问题
这题：最大中等果实
#include <bits/stdc++.h>
using namespace std;
int main (){
int n;
cin >>n;
int k;
cin >>k;
int a[1010];
for (int i = 0; i < n; i++){
cin >> a[i];
}
while (k--){
sort(a,a+n);
a[n>>1]++;
}
sort (a,a+n);
cout <<a[n>>1];
}
这个：小码君的作业本大作战
#include <bits/stdc++.h>
using namespace std;
struct work{
int price, num;
}a[10000000];
bool cmp (work x, work y){
if (x.price != y.price)return x.price < y.price;
return x.num > y.num;
}
int cnt,sum;
int main (){
int n,k;
cin >> n >>k;
for (int i = 0; i < k; i++){
cin >> a[i].price >>a[i].num;
}
sort (a,a+k,cmp);
int ans=0;
int cost=0;
for (int i = 0; i < k; i++){
if (ans + a[i].num <= n){
ans += a[i].num;
cost += a[i].num * a[i].price;
}else{
cost += a[i].price * (n - ans);
break;
}
}
cout <<cost;
}
5.贪心区间排序
拯救迷失的动物：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct s{
int l,r;
}a[1000000];
bool cmp (s x, s y){
return x.r < y.r;
}
signed main (){
int n;
cin >>n;
for (int i = 0; i < n; i++){
cin >>a[i].l>> a[i].r;
}
sort (a,a+n,cmp);
int ans = 0, end = -2e8;
for (int i = 0; i < n; i++){
if (end < a[i].l){
ans ++;
end = a[i].r;
}
}
cout <<ans;
return 0;
}
好了，今天的日记就到这里了，大家记得关注我哦
我一定回关
这里空空如也
有帮助，赞一个