[CF1011X]Codeforces Round #499(Div.2)

题目链接

http://codeforces.com/contest/1011

A. Stages

大意

从\(n\)个字母中取出\(k\)个字母,使得任意两个字母的序数差大于等于2。定义一个字母的花费为该字母的序数,求总共的最小花费。

题解

将字符串排序后,模拟即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[55];
int main()
{
 int n,k,ans=0,cnt=1;
 char c;
 scanf("%d%d",&n,&k);
 scanf("%s",s);
 sort(s,s+n);
 c=s[0];
 ans+=c-'a'+1;
 for(int i=1;i<n;i++)
 {
  if(cnt==k)break;
  if(s[i]-c>=2)c=s[i],ans+=c-'a'+1,cnt++;
 }
 if(cnt==k)printf("%d",ans);
 else printf("-1");
 return 0;
}

B. Planning The Expedition

大意

一共有\(m\)包食物,每种食物都有一个类型。现在一共有\(n\)个人,每个人每天必须吃种类相同的食物。问这些食物最多可以吃几天。

题解

这道题既可以二分答案,当然也可以贪心。

先将各种食物的数量按降序排序。然后我们从大到小枚举最大探险天数(显然,最大探险天数不会超过\(m\),即不会超过100天),计算在最大探险天数下,能吃上饭的人的数量\(num\)。当\(num>n\)时,这时的最大探险天数即为答案。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[105],n,m,t[105],cnt;
bool cmp(int a,int b)
{
 return a>b;
}
int main()
{
 scanf("%d%d",&n,&m);
 if(n>m)
 {
  printf("0");
  return 0;
 }
 for(int i=1;i<=m;i++)
 {
  scanf("%d",&a[i]);
  t[a[i]]++;
  if(t[a[i]]==1)cnt++;
 }
 sort(t,t+101,cmp);
 for(int i=100;i>0;i--)
 {
  int num=0;
  for(int j=0;j<=cnt;j++)
   num+=t[j]/i;
  if(num>=n)
  {
   printf("%d",i);
   return 0;
  }
 }
}

C. Fly

大意

火箭要搭载\(m\)吨重的载荷,要经过\(2n\)个星球,每个星球都有一个起飞和降落时消耗的燃油系数\(a\)和\(b\).

举例来说,假如载荷为9吨,燃油为3吨,起飞时的燃油系数为8,那么要消耗\(\)(9+3)/8=1.5\(\)吨的燃油。

求出完成航程要搭载的燃料质量的最小值,如果无解,输出-1。

题解

我们可以从后往前倒推出燃油质量,于是就变成了简单数学计算题。

显然,当系数为1时,是无解的。

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1005],b[1005];
bool is_equal(double x,double y)
{
 return abs(x-y)<=1e-9;
}
double solve(int x,double y)
{
 if(x==1||is_equal(-1,y))return -1;
 return y+y*1.0/(x-1);
}
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
  scanf("%d",&a[i]);
 for(int i=1;i<=n;i++)
  scanf("%d",&b[i]);
 double f=m;
 f=solve(b[1],f);
 f=solve(a[n],f);
 for(int i=n-1;i>=1;i--)
 {
  f=solve(b[i+1],f);
  f=solve(a[i],f);
 }
 if(is_equal(-1,f))printf("-1");
 else printf("%.10lf",f-m);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注