「Day 2—贪心问题&分治&前缀和」

贪心问题

定义

顾名思义，越贪越好。。。

习题

P1094 [NOIP2007 普及组] 纪念品分组

思路

简单来说：最少的+最多的，利用双指针。

代码

#include<algorithm>
#include<iostream>
using namespace std;

int w,n;
int p[30005];

int main(){
    cin>>w;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    sort(p+1,p+n+1);
    int l=1,r=n,ans=0;
    while(l<=r){
        if(p[l]+p[r]<=w){
            l++;
            r--;
            ans++;
        }
        else{
            r--;
            ans++;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

P1803 凌乱的yyy / 线段覆盖

思路

按照右端点进行排序，每次选择右端点，判断当前的右端点是否比下一个的左端点小，如果小，证明其需要更新。

代码

#include<iostream>
#include<algorithm>
using namespace std;

struct node{
    int x,y;
}p[1000005];
int n;
bool cmp(node x,node y){
    return x.y<y.y;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1,cmp);
    int id=0,ans=0;
    for(int i=1;i<=n;i++){
        if(id<=p[i].x){
            id=p[i].y;
            ans++;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

P1181 数列分段 Section I

思路

每次从前向后加，如果大于m，则更新为当前值，否则就加上。

代码

#include<iostream>
using namespace std;

int n,a[100005];
int ans=0,m,cnt=0;

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(cnt+a[i]>m){
            ans++;
            cnt=a[i];
        }
        else cnt+=a[i];
    }
    cout<<++ans<<"\n";
    return 0;
}