贪心四部曲

2024-01-25 00:48

文章标签 贪心四部曲

本文主要是介绍贪心四部曲，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

NYOJ71 独木舟上的旅行

问题描述
n个人乘船，要求在独木舟最大承载量w内求出需安置的最少的独木舟数，限制每条船最多乘坐两人。
问题分析
在整体中首先需要考虑体重最轻的一个人，如果没有人可以与他一起同坐一艘船，则必须每个人独自乘坐；不然根据贪心的策略，应在能
和他一起乘船的人中选择最重的那一个人与他一起乘船。

代码实现

#include <iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#include<cmath>
using namespace std;
int T,m,n;
int a[306];
int total=0;
void cacut()
{int i=0,j=n-1;while(i<=j){if(a[i]+a[j]<=m){i++;j--;}elsej--;total++;}
}
int main()
{scanf("%d",&T);while(T--){total=0;memset(a,0,sizeof(a));scanf("%d%d",&m,&n);for(int i=0; i<n; i++){scanf("%d",&a[i]);}sort(a,a+n);cacut();printf("%d\n",total);}return 0;
}

POJ2586 Y2K Accounting Bug

问题描述
理解了好久的题意T_T 一家公司一年中每月要么盈利为s，要么亏损为d。其每连续五个月公布一次盈利情况，那么一年中公布8次，已知该
公司八次公布均为亏损，问该公司全年是否可能盈利，若是输出可能盈利的最大值，否则输出Deficit。
问题分析
在保证每连续五个月亏损的前提下，使得盈利月份更多，输出最佳情况。
case 1: ssssdssssdss 需满足 4s-d<0 即共盈利10个月盈利：10s-2d;
case 2: sssddsssddss 需满足3s-2d<0 即共盈利 8 个月盈利：8s-4d;
case 3: ssdddssdddss 需满足3s-3d<0 即共盈利 6 个月盈利：6s-6d;
case 4: sddddsddddsd 需满足s-4d<0 即共盈利 3 个月盈利：3s-9d;
case 5: dddddddddddd 无盈利返回-1。

代码实现

#include <iostream>
#include<cstdio>
using namespace std;
int judge(int s,int d)
{if(4*s-d<0)return 10*s-2*d;if(3*s-2*d<0)return 8*s-4*d;if(2*s-3*d<0)return 6*s-6*d;if(s-4*d<0)return 3*s-9*d;return -1;
}
int main()
{int s,d;while(~scanf("%d%d",&s,&d)){if(judge(s,d)>0)printf("%d\n",judge(s,d));elseprintf("Deficit\n");}return 0;
}

POJ2109 Power of Cryptography

问题描述
知 n、p，求 k 使得 k^n=p。
问题分析
开始没有考虑太多，直接double用函数开方AC，觉得好大的水题。后来搜了一下题解，感叹二分+高精度为何物。也就是在k值所可满足的
最小值与最大值范围内二分查找，直至找到满足条件的k值。

代码实现

#include <iostream>
#include<cstdio>
using namespace std;
#include<cmath>
int main()
{double n,p;int t;while(~scanf("%lf%lf",&n,&p)){printf("%.0lf\n",pow(p,1/n));}return 0;
}

//二分法
#include <iostream>
#include<cstdio>
using namespace std;
#include<cmath>
#define eps 0.0000000001
int main()
{double n,p,k;double l,r,m;while(~scanf("%lf%lf",&n,&p)){l=0,r=1000000000;while(l+eps<=r){m=(l+r)/2;if(pow(m,n)-p>=0)r=m;elsel=m;}printf("%.0lf\n",m);}return 0;
}

POJ1328 Radar Installation

问题描述
在x轴上装置雷达，可以覆盖以d为半径的圆周区域，同时有n个岛屿(坐标为(x,y))，求最少需要安置多少雷达，才能覆盖所有的岛屿。
问题分析
1、求出该小岛被覆盖时雷达所能安置的区间，即[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)]；
2、按照区间的左端点升序排列；
3、判断所需雷达数：若下一个区间的左端点大于当前区间的右端点，则表明不存在重合区域，雷达数+1；若下一个区间的右端点小于当前
区间的右端点，说明雷达覆盖范围为较小区间，则需更新当前雷达覆盖范围。

代码实现

#include <iostream>
#include<cstdio>
using namespace std;
#include<algorithm>
#include<cmath>
struct region
{double left;double right;
} a[1002];
bool cmp(region a,region b)
{return a.left<b.left;
}
int main()
{int n,j=1;int total;double temp,d,x,y;bool s;while(~scanf("%d%lf",&n,&d)&&n&&d){s=false;for(int i=0; i<n; i++){scanf("%lf%lf",&x,&y);if(y>d||d<0) s=true;a[i].left=x-sqrt(d*d-y*y);a[i].right=x+sqrt(d*d-y*y);}if(s){printf("Case %d: -1\n",j);j++;continue;}sort(a,a+n,cmp);temp=a[0].right;total=1;for(int i=1; i<n; i++){if(a[i].left>temp){total++;temp=a[i].right;}else if(a[i].right<=temp)temp=a[i].right;}printf("Case %d: %d\n",j,total);j++;}return 0;
}