二分贪心题解
题目链接 https://vjudge.net/contest/279985#overview
密码 guass
A - 发工资咯：）HDU - 2021
•问题分析： 有点像贪心算法的地方，实际上要简单很多。尽可能用大面值币种发工资是常识。用贪心算法来做则需要先将币值从大到小排序，由于币值数组是人为设定的，就省去排序了。
对于每一个工资值，用币值从大到小处就是需要的张数。看着程序应该是可以理解的。 其他的就是数据输入格式，数据输出格式，程序书写格式的问题，相对都简单了。
#include<stdio.h>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(!n)
break;
int sum=0;
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
sum+=x/100;
x%=100;
sum+=x/50;
x%=50;
sum+=x/10;
x%=10;
sum+=x/5;
x%=5;
sum+=x/2;
x%=2;
sum+=x;
}
printf("%d\n",sum);
}
return 0;
}
B - 今年暑假不AC
问题分析：
典型的贪心算法题，
若干个电视节目，自然要按时间顺序来看。为了看更多的节目，需要尽快看完一个节目再看另外一个节目，多看短节目才能看更多的节目。
先sort按截止日期排一下，如果下一个begin>=end选，否则不选，注意记录上一个选的哪个
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
int begin_,end_;
};
node p[1005];
bool cmp(node a,node b)
{
return a.end_<b.end_;
}
int main()
{
int t;
while(scanf("%d",&t)!=EOF)
{
if(!t)
break;
for(int i=0;i<t;i++)
{
scanf("%d%d",&p[i].begin_,&p[i].end_);
}
sort(p,p+t,cmp);
int last=0;
int sum=1;
for(int i=1;i<t;i++)
{
if(p[i].begin_>=p[last].end_)
{
sum++;
last=i;
}
}
printf("%d\n",sum);
}
}
C - 卡片游戏
https://www.cnblogs.com/Draymonder/p/6944479.html
C++字符串 string 学习
string.length 就是strlen(string)
用string 主要是为了 方便在前面加还是在后面加数
按理说 比第一个数大的放右边，比第二个数小的放左边就可以了‘
但是第一个数不能为 0
所以，我的思路是 先把第一个数给找出来 （不是0的最小的）， 记录下他的位置 然后它前面的（它上面的数）按照（ 比第一个数大的放右边，比第二个数小的放左边）排，它后面的 直接放他后面
比如说
9876105432
第一个数就是 1
去除1之后 9876 05432 两部分
前面的排好6789 后面的不变05432 第一个 1
就是1678905432
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
for(int i=0; i<t; i++)
{
string str,s="";
cin>>str;
char head='9';
int flag;
for(int i=0; i<str.length(); i++)
{
if(str[i]!='0'&&head>=str[i])
{
flag=i;
head=str[i];
}
}
for(int i=0; i<str.length(); i++)
{
if(i==flag)
continue;
if(i>flag)
{
s=s+str[i];
continue;
}
if(i==0||str[i]>s[0])
{
s=s+str[i];
}
else
{
s=str[i]+s;
}
}
cout<<head+s<<endl;
}
}
D - 补提交卡
补签是肯定连续的天数才能让连签天数最大
看看连续的是哪几天就可以
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int day,buqian;
int a[105];
scanf("%d%d",&day,&buqian);
a[0]=0;
for(int i=1;i<=day;i++)
{
scanf("%d",&a[i]);
}
if(buqian>=day)
{
printf("100\n");
continue;
}
int ans=0;
for(int i=1;i<=day-buqian;i++)
{
ans=max(ans,a[i+buqian]-a[i-1]-1);
}
printf("%d\n",ans);
}
}
E - coins
最少的贪心 最多的根据最少的
根据剩下的钱拼凑
#include <iostream>
#include <string.h>
#include <stdio.h>
#include<algorithm>
using namespace std;
const int INF=1000000000;
struct q
{
int x,y;
} a[10];
int main()
{
int j,T,i,minn,maxx,s,p,sum,z[10],t,X;
a[1].x=1;
a[2].x=5;
a[3].x=10;
a[4].x=50;
a[5].x=100;
scanf("%d",&T);
while(T--)
{
sum=0;
scanf("%d%d%d%d%d%d",&p,&a[1].y,&a[2].y,&a[3].y,&a[4].y,&a[5].y);
s=p;
memset(z,0,sizeof(z));
for(i=5; i>=1; i--)
{
if(s>=a[i].x)
{
sum+=min(s/a[i].x,a[i].y);
z[i]=min(s/a[i].x,a[i].y);
s=s-a[i].x*min(s/a[i].x,a[i].y);
}
}
if(s!=0)
{
printf("-1 -1\n");
continue;
}
minn=sum;
for(i=5; i>=1; i--)
{
if(z[i])
{
sum=0;
for(j=i-1; j>=1; j--)
{
if(a[j].y-z[j])
{
sum+=(a[j].y-z[j])*a[j].x;
}
}
if(sum>=a[i].x)
{
X=min(sum/a[i].x,z[i]);
z[i]-=X;
t=X*a[i].x;
for(j=i-1; j>=1; j--)
{
if(a[j].y-z[j])
{
X=min(t/a[j].x,a[j].y-z[j]);
z[j]+=X;
t=t-X*a[j].x;
}
}
}
}
}
sum=0;
for(i=1; i<=5; i++)
{
if(z[i])
{
sum+=z[i];
}
}
maxx=sum;
printf("%d %d\n",minn,maxx);
}
return 0;
}
F - Cable master
多组数据，n个小棒，分成k段，最长多长？
不能短于0.01，如果分不出来，输出”0.00”
假设长度为mid判断是否能分成k段
能的话mid--right 不能的话 left 到mid
二分 卡了半天精度
注意输出
#include <iostream>
#include <string.h>
#include <stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-8
int main()
{
int n,d;
while(scanf("%d%d",&n,&d)!=EOF)
{
double l=0.0;
double r=100001.0;
double a[10005];
for(int i=0; i<n; i++)
{
scanf("%lf",&a[i]);
}
double mid;
while(l+eps<=r)
{
mid=(l+r)/2.0;
int sum=0;
for(int i=0; i<n; i++)
{
sum+=(int )(a[i]/mid);
}
if(sum>=d)
l=mid;
else
r=mid;
}
printf("%.2f\n",floor(r*100)/100.0);
}
}
G - Monthly Expense
二分答案 贪心
题意：有N个数分成M堆，每一堆数必须是相邻的，问所有分法中堆中所有数的和的最大值的最小值是多少？
解题思路：最大值最小，二分解决
枚举的最小值是每天还的钱中的最大值，最大值是每天还的钱的总和
因为每次枚举的钱肯定是大于等于每天还的钱中的最大值的，所以最多可以分成N个集合，然后在算出最小的集合，最小的集合数量就是每一个集合尽量包含更多的天
#include<cstdio>
#include<iostream>
using namespace std;
const int LEN=100050;
int main()
{
int n, m, money[LEN];
while( scanf("%d%d", &n, &m)!=EOF )
{
int maxv=0, sum=0;
for(int i=0; i<n; i++)
{
scanf("%d", money+i);
if( money[i]>maxv )
maxv=money[i];
sum+=money[i];
}
int high=sum, low=maxv, mid;
while( high>low )
{
mid=(high+low)>>1;
int count=1, w=0;
for(int i=0; i<n; i++)
{
w+=money[i];
if( w>mid )
{
count++;
w=money[i];
}
}
if( count>m )
low=mid+1;
else
high=mid-1;
}
printf("%d\n", high);
}
return 0;
}
H - Light Bulb
https://blog.csdn.net/controlbear/article/details/54237388 题解
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const double esp=1e-8;
double H,h,D;
double cal(double x)
{
return D-x+H-(H-h)*D/x;
}
double three_devide(double l,double r)
{
double left=l,right=r,mid,midmid;
while (left+esp<right)
{
mid=(right+left)/2;
midmid=(right+mid)/2;
if (cal(mid)>=cal(midmid))
right=midmid;
else
left=mid;
}
return cal(right);
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%lf%lf%lf",&H,&h,&D);
double l=D-h*D/H,r=D;
double ans=three_devide(D-h*D/H,r);
printf("%.3f\n",ans);
}
return 0;
}
I - Integer Sequence Dividing
判断1--n的和是奇数 输出1 偶数 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1000010;
const int inf=0x3f3f3f3f;
ll n;
int main()
{
cin>>n;
ll ans=(n*(1+n))/2;
if(ans&1)
{
cout<<1<<endl;
}else
{
cout<<0<<endl;
}
return 0;
}
投递深圳同为数码等公司10个岗位
