#创作计划#阳坡湖集训笔记day1
2025-07-23 19:28:18
发布于：浙江
贪心
由局部最优，到全局最优
字典序比较：
1.字符串左对齐
2.字母少的字符串字典序小
3.数字<大写<小写
4.每一位比较ASCLL码
sort()函数
sort(a,a+n,cmp)(不写cmp也可以默认升序)
sort(aa+n,greater<int>())(降序排序)
cmp
bool cmp(数据类型 x，数据类型 y){
return x>y;(降序)
return x<y;(升序，不写cmp默认是升序)
}
sort()时间复杂度O(nlogn)n倍logn
字符串排序
sort(s.begin(),s.end());
sort(s.begin(),s.end(),greater<int>());
结构体
关键字 struct
方式：
struct 想新建的数据类型的名称{
数据类型 成员名1；
数据类型 成员名2；
数据类型 成员名3；
……
}；别忘加分号
题目:
在一个神秘的魔法王国里，两个强大的巫师，
吉娜 和
安度因，他们在打一起打副本的时候遇到了一个难题。
现在每个巫师手里都有一个装满魔法符文的袋子，这些符文由小写英文字母分别表示为字符串
s 和 t。他们可以通过重新排列各自字符串中的字符来获得一个新的符文组合。
如果两位巫师可以在重新排列字符串
s 和 t 后让
s 的字典序 <
t 的字典序就可以解决这个难题，然后输出YES，否则输出NO。
这一题就是字典序和sort
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
string s,v;
cin>>t;
while(t--){
cin>>s>>v;
sort(s.begin(),s.end());
sort(v.begin(),v.end(),greater<char>());
if(s<v)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
由于要让s的字典序<t的字典序，所以s要降序，才能字典序更大，t是升序，字典序更小
下一题:
昱栋同学刚刚放学回家，快饿死了！！但是他又不想吃太多（似乎在减肥），现在有
N 种食物，其中第
i 种的甜度为 A i ，咸度为 Bi 。昱栋同学可以按任意顺序排列这
N 种食物，然后依次品尝。每次他会从当前顺序开始依次吃下去，直到甜度之和大于
X 或者咸度之和大于
Y 为止。
请计算昱栋同学吃的最少食物数量，使得吃下的食物的甜度或咸度满足停止条件。
首先，他停止的前提有两个甜度之和大于x，或咸度之和大于y
那么尽可能少的吃，要降序排（甜/咸度），这样才能尽可能少吃东西；
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
int main(){
long long n,x,y,sum=0,sum1=0;
int a[N],b[N];
cin>>n>>x>>y;
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,greater<int>());
sort(b+1,b+1+n,greater<int>());
for(int i = 1;i <= n;i++){
sum+=a[i];
sum1+=b[i];
if(sum>x||sum1>y){
cout<<i;
break;
}
}
return 0;
}
第三题，额跳过，第四题：
在奇幻的果园中，有一棵神奇的果树，果树上挂满了大小不一的果实，果实的重量形成了一个长度为
n（且n 为奇数）的数组
a。每个果实的重量都可以通过注入灵气来增加，每次注入灵气会让果实的重量增加1。
果农昱栋希望通过注入灵气的方式，让果实的 中等重量（也就是数组排序后中间果实的重量）尽可能大！
然而，灵气是有限的，昱栋最多只能注入 k 点灵气。请帮助昱栋计算，在灵气用完后，果实的 中等重量 最多可以达到多少？
首先，中间的果实要是最大，且不能超过后面的
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n,k;
cin>>n>>k;
int a[n+5];
for(int i = 1;i <= n;i++)cin>>a[i];
while(k--){
sort(a+1,a+1+n);
a[n/2+1]++;
}
sort(a+1,a+1+n);
cout<<a[n/2+1];
return 0;
}
代码就是这样
点个赞吧,ac君能置顶或精华吗？球球了!
额还有些题明天再fa
这里空空如也
有帮助，赞一个