henrytb 的博客

henrytb 的博客

ZROI 9.9 贪心

posted on 2018-09-09 13:58:00 | under ZROI |

$$\text{ 贪心 }$$


  • 贪心算法是指对问题求解时,总是做出在当前看来是最好的选择。
  • 也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
  • 贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。
  • 必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
  • 所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

$$\color{blue}\text{ P1056 排座椅(This is a link.下同) }$$

  • 教室是一个矩阵,某些同学之间会交头接耳
  • 交头接耳的同学要么横向相邻要么纵向相邻
  • 现在可以划分K条横向通道,L条纵向通道,让被通道隔开的同学没法交头接耳
  • 求应该划在哪些行之间/哪些列之间

Solution:

  • 行和列显然独立
  • 求出划在第i和i+1行之间能隔掉多少交头接耳的
  • 排个序取前若干大的即可
  • 列也一样

$\color{green}\text{AC Code:}$

#include <bits/stdc++.h>
using namespace std;
int m,n,k,l,d,hang[1005],lie[1005],hangguo[1005],lieguo[1005];
bool usedhang[1005],usedlie[1005];
int main(){
    cin>>m>>n>>k>>l>>d;
    for(int i=1;i<=d;i++){
        int xa,xb,ya,yb;
        cin>>xa>>ya>>xb>>yb;
        if(xa==xb){
            lie[min(ya,yb)]++;
        }
        if(ya==yb){
            hang[min(xa,xb)]++;
        }
    }

    for(int j=1;j<=k;j++){
        int maxn=0,maxx;
        for(int i=1;i<=m;i++){
            if(hang[i]>maxn&&!usedhang[i]){
                maxn=hang[i];
                maxx=i;
            }
        }
        usedhang[maxx]=true;
        hangguo[j]=maxx;
    }
    for(int j=1;j<=l;j++){
        int maxn=0,maxx;
        for(int i=1;i<=m;i++){
            if(lie[i]>maxn&&!usedlie[i]){
                maxn=lie[i];
                maxx=i;
            }
        }
        usedlie[maxx]=true;
        lieguo[j]=maxx;
    }
    sort(hangguo+1,hangguo+k+1);
    sort(lieguo+1,lieguo+l+1);
    for(int i=1;i<=k;i++){
        cout<<hangguo[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=l;i++){
        cout<<lieguo[i]<<" ";
    }
    return 0;
}

$$\color{blue}\text{ P1209 修理牛棚 }$$

有n个牛棚(可以认为每个牛棚是一个点),要在牛棚上盖上木板,你可以用不超过k块连续的木板,求最小可行的木板总长度。

Solution:

  • 把1块木板断开成两块木板时,可以挖掉某个[i,i+1]的距离
  • 那么把所有相邻元素的差拿出来,从大到小排序
  • 取前k-1大的减掉就行了

$\color{green}\text{AC Code:}$

#include <bits/stdc++.h>
using namespace std;
int m,s,c,cow[205],b[205],ans;
bool bigcmp(int a,int b){
    return a>b;
}
int main(){
    cin>>m>>s>>c;
    for(int i=1;i<=c;i++)cin>>cow[i];
    sort(cow+1,cow+c+1);
    for(int i=1;i<c;i++)b[i]=cow[i+1]-cow[i]-1;
    sort(b+1,b+c,bigcmp);
    ans=cow[c]-cow[1]+1;
    for(int i=1;i<m and i<c;i++)ans-=b[i];
    cout<<ans;
    return 0;
}

$$\text{ 部分背包 }$$

  • 有?个物品,每个物品有个重量 $w_i$ 和价值 $v_i$ 。
  • 你有一个容量为?的背包
  • 一个物品可以放入一部分,重量和价值按比例计算
  • 求最多能放入多少价值的物品

Solution:

  • 优先放?/?尽量大的
  • 如果某个?/?大的没有用完就放了一个?/?小的,把这部分容量换成那个?/?大的,一定会变优

01背包需要??


$$\color{blue}\text{ P1459 三值的排序 }$$

有一个仅由1,2,3组成的序列,求最少需要多少次交换能把它排成升序。

Solution:

  • 排序后的序列分为三个部分:排序后应存储1的部分,排序后应存储2的部分和排序后应存储3的部分。
  • 贪心排序法应交换尽量多的交换后位置正确的(2,1)、(3,1)和(3,2)数对。当这些数对交换完毕后,再交换进行两次交换后位置正确的(1,2,3)三个数。

$\color{green}\text{AC Code:}$

#include <bits/stdc++.h>
using namespace std;
int n,a[1001],a1,a2,a3,sum,kkk;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==1)a1++;
        else if(a[i]==2)a2++;
        else a3++;
    }
    a2+=a1;
    a3+=a2;
    for(int i=0;i<a1;i++){
        if(a[i]==2)for(int j=a1;j<a2;j++)if(a[j]==1){
            swap(a[j],a[i]);
            sum++;
            break;
        }
    }
    for(int i=0;i<a1;i++){
        if(a[i]==3)for(int j=a2;j<a3;j++)if(a[j]==1){
            swap(a[j],a[i]);
            sum++;
            break;
        }
    }
    for(int i=a1;i<a2;i++){
        if(a[i]==3)for(int j=a2;j<a3;j++)if(a[j]==2){
            swap(a[j],a[i]);
            sum++;
            break;
        }
    }
    for(int i=0;i<a1;i++)if(a[i]!=1)kkk++;
    for(int i=a1;i<a2;i++)if(a[i]!=2)kkk++;
    for(int i=a2;i<a3;i++)if(a[i]!=3)kkk++;
    kkk*=2;kkk=kkk/3;
    kkk+=sum;
    cout<<kkk;
    return 0;
}

$$\color{blue}\text{ P1223 排队接水 }$$

  • 有 $n$ 个人排队到一个水龙头前打水,他们装满水桶的时间分别为 $T_1$ , $T_2$ ,… $T_n$ 。
  • 请问应该如何安排他们打水的顺序才能使所有人等待的总时间最少?

Solution:

  • 由于排队时,越靠前面的计算的次数越多,显然越小的排在越前面得出的结果越小。
  • 具体证明:
    排序不等式:倒序积和≤乱序积和≤顺序积和
  • 所以这道题可以用贪心法解答,基本步骤:
    1. 将输入的时间按从小到大排序;
    2. 将排序后的时间按顺序依次放入每个水龙头的队列中;
    3. 统计,输出答案。

$\color{green}\text{AC Code:}$

#include <bits/stdc++.h>
using namespace std;
struct person{
    int t,num;
}a[1005];
int n;
double ans;
bool cmp(person a,person b){
    return a.t<b.t;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].t);
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        printf("%d ",a[i].num);
        ans+=(double)(a[i].t)*(n-i);
    }
    ans/=(double)n;
    printf("\n%.2lf",ans);
    return 0;
}

$$\text{ 经典问题 }$$

  • 有若干个区间
  • 求最多能找出多少不相交的区间

比较容易想到的贪心策略:

  1. 左端点靠左的优先
    反例:[1,100], [2,2], [3,3]

  2. 长度短的优先
    反例:[1,10], [10,11], [11,20]

  3. 右端点靠左的优先
    这个是对的
    But why?

    • 调整法
    • 假设最优解前x-1个都和我们的方案相同,第x个他选了个右端点更靠右的
    • 那么我们把最优解中第x个换成我们的第x个,不会产生矛盾

$$\color{blue}\text{ P1094 纪念品分组 }$$

  • 有若干纪念品,每个纪念品有个价值
  • 要把纪念品分成若干组,每组最多2个纪念品
  • 每组的价值和不能超过一个给定的整数
  • 求最少要分多少组

Solution:

  • 贪心策略1:如果最轻的+最重的>限制,则最重的自己分一组,否则把它们分在一组。
  • 贪心策略2:最重的和能跟它匹配的最重的放一组。

$\color{green}\text{AC Code:}$

#include <bits/stdc++.h>
using namespace std;
int w,n,p[30005];
int main(){
    cin>>w>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }
    sort(p+1,p+n+1);
    int left=1,right=n;
    int ans=0;
    while(left<=right){
        if(p[left]+p[right]<=w){
            left++;
            right--;
            ans++;
        }
        else{
            right--;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

$$\color{blue}\text{ P1090 合并果子 }$$

  • 有?堆果子,每堆有个重量
  • 每次可以合并两堆,付出的代价是它们重量之和
  • 要把?堆果子合成一堆,问最小代价

Solution:

  • 每次合并重量最小的两堆
  • 暴力 $O(n^2)$ ,用个数据结构搞一搞就能 $O(nlogn)$

$\color{green}\text{AC Code:}$

#include <iostream>
#include <cstdio>
#include <queue>
#include <functional>
using namespace std;
int n,a,ans;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a),q.push(a);
    for(int i=1;i<=n-1;i++){
        int x=q.top();
        q.pop();
        int y=q.top();
        q.pop();
        int c=x+y;
        q.push(c);
        ans+=c;
    }
    printf("%d",ans);
    return 0;
}

这就是2叉哈夫曼树

扩展:k叉哈夫曼树