[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;
}