今天听了学长分享的贪心 我来复盘督促一下自己呗
题目表述：
#include <cstdio>
using namespace std;
int n,m,ans=1;//ans的初值要为1
int main(){
scanf ("%d %d",&n,&m);
int k=0;
while (n--){//完全的边读边做
int a;
scanf ("%d",&a);//读入a
if (k+a<=m){//判断k+a是否大于m如果小于等于，k就要加上a
k+=a;
}
else{
ans++;
k=a;//如果大于，ans要加1，然后a独立为一段；
}
}
printf ("%d\n",ans);//做完之后输出，结束
}
题目表述：
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6;
int a[N];
int check(int mid){
int cnt=1;//开始的初值必须为1，因为最后一段是加不进去的
int num=0;
for(int i=1;i<=n;i++){
if(num+a[i]<=mid) num+=a[i];
else {
cnt++;
num=a[i];//a[i]独立为一段
}
}
if(cnt<= m) return 1;//需要缩小范围就改变有右端点
return 0;
}
//求最大值中的最小
int main(){
cin>>n>>m;
int maxn=0,sum=0;
for(int i=1;i<=n;i++) {
cin>>a[i];
maxn=max(maxn,a[i]);
sum+=a[i];
}
int l=maxn,r=sum;
while(l<r){
int mid = (l+r) >>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
先补充点优先队列
c++优先队列priority_queue
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出
他和queue不同的就在于我们可以自定义其中数据的优先级
让优先级高的排在队列前面
优先出队,用堆来实现
** priority_queue<int> qi; ** 从大到小
等同于 priority_queue<int, vector<int>, less<int> > a;
从小到大这里一定要有空格，不然成了右移运算符↓↓
** priority_queue<int, vector<int>, greater<int> >qi2;**
和队列基本操作相同:
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素 = 删除
swap 交换内容
题目表述：
合并果子
题意：：这道题只需要把最小的两个果堆加起来就可以了，想到优先队列
#include <bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
int n,x;
int ans=0;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x;
q.push(x);//1 2 9
}
while(q.size()>=2){
int a=q.top();q.pop();//2 9 9(访问再删除)
int b=q.top();q.pop();//9 空
ans+=(a+b);//1+2=3 3+3+9=15
q.push(a+b);//3 9 12
}
cout<<ans<<endl;
return 0;
}
补充（贪心） 乐呵采蘑菇
题意：
也就是枚举小水潭从小开始，如果手臂半径大于小水潭那么就拿到，这样我们就可以确保以最小的去拿到，直接采摘人全部没有。
#include <bits/stdc++.h>
using namespace std;
#define N 20001
int a[N],b[N];
int main()
{
int n,m;
ios::sync_with_stdio(false);
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=0;i<m;i++)scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+m);
int i,res=0,j=0;
for(i=0;i<m;i++)
{
if(a[j]<=b[i])
{
res+=b[i];
j++;
if(j==n)break;
}
}
if(j<n)puts("Sad!");
else printf("%d\n",res);
}
}
题目表述：
老鼠与猫的交易
题意：（贪心）选择 奶酪/猫食 尽量大的（选择性价比高的）
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r;
double num;
}a[1010];
bool cmp(node a,node b){
if(a.num!=b.num ) return a.num>b.num;
}
int main(){
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++) {
cin>>a[i].l>>a[i].r;
a[i].num=a[i].l*1.0/a[i].r;
}
sort(a+1,a+1+n,cmp);
double num=0;
for(int i=1;i<=n;i++){
if(m>=a[i].r){
num+=a[i].l;
m-=a[i].r;
}
else {
num+=m*1.0/a[i].r*a[i].l;//要把int的m转化成double
break;
}
}
printf("%.3lf",num);
}
题目表述：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int main(){
int a[N], b[N], n, w;
while(scanf("%d", &n)){
if( n == 0) break;
for(int i = 1; i <= n; i++) scanf("%d", a+ i);
for(int i = 1; i <= n; i++) scanf("%d", b + i);
sort(a+1, a+n+1, greater<int>());
sort(b+1, b+n+1, greater<int>());
w = 0, a[0] = 1, b[0] = 1;
for(int i = 1; i <= n; i++){
if(a[a[0]] > b[b[0]]) w++, a[0]++, b[0]++;
else b[0]++;
}
printf("%d\n", (2*w-n)*200);
}
return 0;
}
题目表述:
搬桌子 题意：（找重叠部分）输出重叠最多的次数
注意： 1，2是相同位置
#include<bits/stdc++.h>
using namespace std;
int main()
{
int i,j,T,N,s,t;
int r[200];
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
memest(r,0,sizeof(r));
for(i=0;i<N;i++)
{
scanf("%d%d",&s,&t);
if(s>t){
j=s;s=t;t=j;
}
for(j=(s-1)/2;j<=(t-1)/2;j++)
r[j]++;
}
t=r[0];
for(i=1;i<200;i++)
if(t<r[i]) t=r[i];
printf("%d\n",t*10);
}
return 0;
}
题目表述：(事件序列问题)
今年暑假不AC
题意：（找最早结束的的节目）对节目结束时间进行排序
#include<bits/stdc++.h>
using namespace std;
struct node{
int s,e;
}a[1000];
bool cmp(node a,node b){
if(a.e!=b.e )return a.e<b.e;
}
int main()
{
int n;
while(cin>>n){
if(n==0) break;
for(int i=0;i<n;i++)
cin>>a[i].s>>a[i].e;
sort(a,a+n,cmp);
int cnt=1;
int l=a[0].s,r=a[0].e;
for(int i=1;i<n;i++){
if(a[i].s>=r) {
cnt++;
r=a[i].e;
}
}
cout<<cnt<<endl;
}
return 0;
}
题目表述：（可图性判定）
今天我们来学习一下递推算法吧 （最近太累了过两天再完善吧）
斐波那契数列(数据范围0<n<50)(1,1,2,3,5,8…)
x[n]=x[n-1]+x[n-2];
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[60];
int n;
int main()
{
x[1]=1;
x[2]=2;
for(int i=3;i<=51;i++)
{
x[i]=x[i-1]+x[i-2];
}
cin>>n;
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
cout<<x[b-a]<<endl;
}
return 0;
}
亿点点递归小补充：
斐波那契数列改进（1,3,5,11…）
