算法设计与分析复习（第7章 贪心法）

  • 开发
  • 19

7-1 h0216.基站

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 检查在最小距离为minDistance的情况下是否可以安装所有的基站
bool canInstallStations(const vector<int>& positions, int stations, int minDistance) {
    int installedStations = 1; // 已安装的基站数量
    int lastPosition = positions[0]; // 上一个安装基站的位置

    for (int i = 1; i < positions.size(); ++i) {
        if (positions[i] - lastPosition >= minDistance) {
            ++installedStations;
            lastPosition = positions[i];
        }
    }

    return installedStations >= stations;
}

// 二分查找最大最小距离
int binarySearchMaxMinDistance(const vector<int>& positions, int stations) {
    int low = 0;
    int high = positions.back();
    int maxMinDistance = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canInstallStations(positions, stations, mid)) {
            maxMinDistance = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return maxMinDistance;
}

int main() {
    int L, S;
    while (cin >> L >> S && L != 0 && S != 0) {
        vector<int> positions(L);
        for (int i = 0; i < L; ++i) {
            cin >> positions[i];
        }

        sort(positions.begin(), positions.end());

        int maxMinDistance = binarySearchMaxMinDistance(positions, S);
        cout << maxMinDistance << endl;
    }

    return 0;
}

7-2 h0145. 会议安排

#include<bits/stdc++.h>
using namespace std;

struct meet{
    int s,e;
}a[10000];

bool cmp(meet a,meet b){
    return a.e<b.e;
}

int main(){
    int n;
    int x;
    cin>>n;
    while(n--){
        cin>>x;
        int i;
        for(i=1;i<=x;i++){
            scanf("%d%d",&a[i].s,&a[i].e);
            
        }
        a[0].s=-1;a[0].e=-1;
        sort(a+1,a+1+x,cmp);
            int num=1;
        int j=1;
        for(i=2;i<=x;i++){
            if(a[i].s>=a[j].e){
                num++;
                j=i;
            }
        }
        cout<<num<<endl;
    }
    return 0;
}

7-3 h0153. 挑剔程度

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
typedef long long int ll;
using namespace std;
int main(){
    ll s[20010]={0};
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>s[i];
    if(n<=k)
        cout<<"0"<<endl;
    else{
        sort(s,s+n);
    cout<<s[n-k-1]<<endl;
    }
    return 0;
}

7-4 h0154.加勒比海盗船——最优装载问题

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int c,n;
        cin>>c>>n;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            v.push_back(temp);
        }
        sort(v.begin(),v.end());
        int sum=0;
        int res=0;
        for(int i=0;i<n;i++)
        {
            sum+=v[i];
            if(sum<=c)
            {
                res++;
            }
            else
            {
                break;
            }
        }
        cout<<res<<endl;
    }
}

7-5 h0297. 包

#include<iostream>
using namespace std;
int main(){
    int N,a,b,c,d,e,f,y,x;
    int u[4]={0,5,3,1};
    while (1){
        cin>>a>>b>>c>>d>>e>>f;
        if (a==0 && b==0 && c==0 && d==0 && e==0 && f==0  ) break;
        N=f+e+d+(c+3)/4; 
        y=5*d+u[c%4];
        if (b>y)    N+=(b-y+8)/9;
        x=36*N-36*f-25*e-16*d-9*c-4*b;
        if (a>x) N+=(a-x+35)/36;    
        cout<<N<<endl;
    }
    return 0;
}

7-6 h0329. 肥猫

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1000;
struct JavaBean{
    double weight;
    double cost;
};
JavaBean arr[MAXN];
bool Compare(JavaBean x,JavaBean y){
    return (x.weight/x.cost)>(y.weight/y.cost);//降序 
}
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        if(m==-1&&n==-1)
            break;
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&arr[i].weight,&arr[i].cost);
    }
    sort(arr,arr+n,Compare);//性价比降序排列
    double answer=0;
    for(int i=0;i<n;++i){
        if(m>=arr[i].cost){//全部买 
            m-=arr[i].cost;
            answer+=arr[i].weight;
        }
        else{//部分买
            answer+=arr[i].weight*(m/arr[i].cost);
            break;
        }
    } 
    printf("%.3f\n",answer);
    }
    return 0;
}

7-7 h0327. 穿墙术

#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX = 110;
int l[MAX],r[MAX],wall[MAX],mark[MAX];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(wall,0,sizeof(wall));
        memset(mark,0,sizeof(mark));
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
        {
            int m1,m2;        // 两个无用的变量（代表的是墙的所在行）
            scanf("%d%d%d%d",l+i,&m1,r+i,&m2);
            if(l[i] > r[i]) swap(l[i],r[i]);
            for(int j=0;j<105;j++)
            {
                if(l[i]<=j && j<=r[i])        // 如果在第j列这个位置存在墙体
                    wall[j]++;                // 第j列的墙体厚度增加1
                else if(j>r[i]) break;        // 一次只输入了一条墙，r[i]后面没有了，就不用管了
            }
        }

        int ans=0;
        int maxright,mr;
        for(int i=0;i<105;i++)            // 墙的长度
        {
            while(wall[i] > k)
            {
                maxright = 0;
                for(int j=0;j<n;j++)
                    if(l[j] <= i && i <= r[j] && !mark[j])  // 找从该列开始右边最长的墙
                        if(maxright < r[j])
                        {
                            maxright = r[j];
                            mr = j;
                        }
                mark[mr] = 1;        // 表示该条墙已经被删除了，同时答案加1
                ans++;
                for(int z=i;z<=maxright;z++)   // 墙体厚度减1
                    wall[z]--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

7-8 h0204. 圣诞老人的礼物

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct gift{
int value;
int weight;
double density;
}gf[101];
bool cmp(gift f1,gift f2){  //按照单重价值从大到小排序
return f1.density > f2.density;
}
int main(){
int n,w;
cin>>n>>w;
for(int i=0;i<n;i++){
    cin>>gf[i].value>>gf[i].weight;
    gf[i].density=1.0*gf[i].value/gf[i].weight;
}
sort(gf,gf+n,cmp);
double totw=0,totv =0; //注意到w为int型，可拆分为double型
//所以新建一个double型保存背包剩余重量
    for(int i=0;i<n;i++){
        if(totw + gf[i].weight<=w){
            totw+=gf[i].weight;
            totv+=gf[i].value;
        }else{
            totv+=gf[i].density *(w-totw);
            totw = w;
            break;
        }
    }
printf("%.1lf",totv);
return 0;
}

7-9 h0205. 电池的寿命

#include<bits/stdc++.h>
using namespace std;
int a[1005];
int main()
{
int n;
while(cin>>n){
    int max=-1,sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum=sum+a[i];
        if(max<a[i]){
            max=a[i];
        }
    }
    if((sum-max)<max){
        printf("%.1f\n",(sum-max)*1.0); 
    }
    else{
        printf("%.1f\n",(sum-max-max)*1.0/2+max);
    }
}
return 0;
}

7-10 h0206. 区间选点

#include<bits/stdc++.h>
using namespace std;
struct xx{
int a,b;
}s[40005];
int cmp(xx x,xx y){
    if(x.b==y.b)return x.a<y.a;
    return x.b<y.b;
}
int main(){
    int n,c=0,j=0;
   cin>>n;
    for(int i=0;i<n;i++){
       cin>>s[i].a>>s[i].b;
    }
    sort(s,s+n,cmp);
    c+=1;
    for(int i=1;i<n;i++){
        if(s[i].a>s[j].b){
            c++;
            j=i;
        }
    }
   cout<<c;
    return 0;
}

7-11 h0207. 雷达问题

#include <bits/stdc++.h>
using namespace std;
struct Point{
double x;
double y;
}point[1000];
bool cmp(Point aa,Point bb){
return aa.x<bb.x;
} 

int main(){
int n,d;
int num=1;
while(cin>>n>>d){//输入多组数据
    int countings=1;
    if(n==0&&d==0) break;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(y>d){
            countings=-1;
        } 
        double t=sqrt(d*d-y*y);//转化为区间的问题，注意代码的表示
        point[i].x=x-t;
        point[i].y=x+t;
        
    }
    if(countings!=-1){
        sort(point,point+n,cmp);//按照左端点的值进行排序
        double s=point[0].y;
        for(int i=0;i<n;i++){//不重合，增加数量，更新右端点。
            if(point[i].x>s){
                countings++;
                s=point[i].y;
            }
            else if(point[i].y<s){//完全被包含则更新右端点；
                s=point[i].y;
            }
        }
    }
cout<<"Case "<<num<<':'<<' '<<countings<<endl;
num++; 

}

}

7-12 h0168. 田忌赛马


#include<iostream>
#include<algorithm>
using namespace std;
int a[100], b[100];//a是田忌，b是秦王
void SelectSort(int* a, int len)
{
for (int i = 0; i < len; i++)
{
    int temp = a[i];
    int min = i;
    for (int j = i+1; j < len; j++)
    {
        if (a[j] < temp)
        {
            min = j;
            temp = a[j];
        }
        
    }
    if (min != i)
    {
        swap(a[i], a[min]);
    }
    
}
}
int main()
{
int n, fastT, fastQ, slowT, slowQ,money;//定义上等马和下等马以及“钱钱”
while (cin >> n && n != 0)//连续输入多组数据
{
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
    }
    slowT = 0;
    slowQ = 0;
    fastT = n - 1;
    fastQ = n - 1;
    money = 0;
    SelectSort(a, n);//选择排序将马儿排位
    SelectSort(b, n);
    for (int i = 0; i < n; i++)//贪心属性为如果上等马打得过上等马，钱钱加一
//，子序列缩短，下等马同理//若都不行，只能劣等打上等，钱钱减一
    {
        if (a[fastT] > b[fastQ])
        {
            money++;
            fastT--;
            fastQ--;
        }else
            if (a[slowT] > b[slowQ])
            {
                money++;
                slowT++;
                slowQ++;
            }
            else
                if(a[slowT]<b[fastQ])
            {
                money--;
                fastQ--;
                slowT++;
            }

    }
    cout << money * 200 << endl;//最后输出钱钱
}
}

7-13 h0169. 鱼塘钓鱼

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n
        ,fo[102]={0},del[102]={0},tonext[102]={0},t
        ,i,j,k,fmx=0;
    cin>>n;//总鱼塘数
    for(i=1;i<=n;i++)scanf("%d",&fo[i]);//初始分钟鱼量
    for(i=1;i<=n;i++)scanf("%d",&del[i]);//每分钟衰减量
    for(i=1;i<=n-1;i++)scanf("%d",&tonext[i]);//到下一鱼塘用时
    cin>>t;//总时间
    for(i=1;i<=n;i++)//遍历最后一个鱼塘的编号
    {
        int ti=t,fiall=0;//fiall是前 i 个鱼塘中的最大钓鱼量
        priority_queue<pair<int,int> >que;//优先队列，除了存储分钟鱼量还需存储对应的鱼塘编号，便于计算下一分钟到鱼量
        pair<int,int>fz;
        for(j=1;j<i;j++)ti-=tonext[j];//计算钓满前 i 个鱼塘的剩余钓鱼时间（减去转移用时）
        for(j=1;j<=i;j++)que.push(make_pair(fo[j],j));//入队初始分钟鱼量
        while(ti>0)//这里没有用while(ti--)是不排除ti已经小于0的情况
        {
            ti--;
            fz=que.top();//最大量出队
            que.pop();
            fiall+=fz.first;
            que.push(make_pair((fz.first-del[fz.second])>=0?(fz.first-del[fz.second]):0,fz.second));
            //入队该池鱼的下一分钟鱼量，避免负数
        }
        if(fiall>fmx){fmx=fiall;}
    }
    printf("%d",fmx);
    return 0;
}

7-14 h0211. 书架

// Created on 2020/2/11
 
/*#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <climits>*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int idata=20000+5;
int step[idata];
int n,m;
int flag;
ll high;
int cnt;
 
inline bool cmp(int a,int b)
{
    return a>b;
}
 
int main()
{
    int i,j;
    cin>>n>>high;
 
    for(i=1;i<=n;i++)
    {
        cin>>step[i];
    }
    sort(step+1,step+1+n,cmp);
 
    while(high)
    {
        for(i=1;i<=n;i++)
        {
            if(high-step[i]>=0)
            {
                high-=step[i];
                cnt++;
            }
            else
                break;
        }
        break;
    }
    if(high)
        cout<<cnt+1<<endl;
    else cout<<cnt<<endl;
 
    return 0;
}

7-15 h0301. 区间分组

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 5;
struct node
{
int l, r;
bool operator <(const node b)const
{
    return r < b.r;
}
}a[N];
int q[N];
int cnt = 0;
int find(int x)
{
int v = -1;
int max = -2e9;
for (int i = 0;i < cnt;i++)
//寻找满足条件的最大端点
if (q[i] < x)
{
    if (max < q[i])
    {
        max = q[i];
        v = i;
    }
}
return v;
}
int main()
{

int n;
cin >> n;
for (int i = 0;i < n;i++)
    cin >> a[i].l >> a[i].r;
sort(a, a + n);
for (int i = 0;i < n;i++)
{
    int t = find(a[i].l);
    if (!cnt || t == -1)
    {//需要多开一组
        q[cnt++] = a[i].r;
    }
    else
    {
        q[t] = a[i].r;
    }
}
cout << cnt;
}

7-16 h0209. 畜栏保留问题

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct A
{
    int s,e,mark;
    bool operator < (const A &a)const
    {
        return e>a.e;
    }
}a[50001];
priority_queue<A>q;
bool cmp(const A &a,const A &b)
{
    if(a.s==b.s)
        return a.e<b.e;
    return a.s<b.s;
}
int x[50001];//标记
int main()
{
    int n;
    scanf("%d",&n);
     for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].s,&a[i].e);
            a[i].mark=i;//先给每头牛一个编号
        }
        sort(a,a+n,cmp);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(q.size()&&q.top().e<a[i].s)
            {
                x[a[i].mark]=x[q.top().mark];
                //能做，结束最早的来做。结束最早的那个人就是当前的那个人。
                q.pop();
                q.push(a[i]);
            }
            else
            {
                sum++;
                x[a[i].mark]=sum;//不能做，就有新加进来的人做
                q.push(a[i]);
            }
        }
        printf("%d\n",sum);
        for(int i=0;i<n;i++)
            printf("%d\n",x[i]);
    return 0;
}

阅读全部

相关推荐

  1. 算法设计与分析复习（第7章 贪心法）

    2024-06-13 14:40:03       20 阅读

  2. 算法设计与分析复习（第5章 回溯法）

    2024-06-13 14:40:03       24 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-13 14:40:03       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-13 14:40:03       100 阅读

  9. 在Django里面运行非项目文件

    2024-06-13 14:40:03       82 阅读

  19. Python语言-面向对象

    2024-06-13 14:40:03       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-06-13 14:40:03       85 阅读

热门阅读

  17. redis 故障处理： 持续更新

    2024-06-13 14:40:03       33 阅读

  19. 探索PostgreSQL：从基础到进阶的实用教程

    2024-06-13 14:40:03       30 阅读

  20. NXP RT1060学习总结 - fsl_flexcan 基础CAN函数说明 -3

    2024-06-13 14:40:03       31 阅读

  21. 【数学】小学公式与概念

    2024-06-13 14:40:03       25 阅读

  23. python迁移数据教程

    2024-06-13 14:40:03       31 阅读

  27. Spring （55）Spring Boot的测试支持

    2024-06-13 14:40:03       38 阅读

  30. SHELL脚本学习（七） 脚本控制(2)

    2024-06-13 14:40:03       30 阅读