2018年2/3月月赛 Day2 石化 题解

发表于 | 分类于

2018年2/3月月赛 Day2 石化 题解

题目背景

漫长战斗终于分出胜负了。

“喂，我可没听说非拼成这样才赢得了。”

七道亡国级禁咒，十一把开刃到自毁程度的帕西瓦尔系列，甚至青年本身没资格动用的勇者剑技最终奥义都已经强行祭出。

假如这样还不能将其灭绝，也无计可施了。

「真是惊天动地啊。身为无力的凡人之躯，却能独自使出此等力量吗？实在可怕。不过，看来要发挥那样的力量，实在不可能毫无代价。」

“啪”的一声，青年脚踝前面的部分已经变成粗糙的石块了。

又是好几声脆响重叠在一起，灰色面积开始沿着他的身体往上蔓延扩散，到了膝盖，到了腿，到了腰，还在继续往上。

题目描述

威廉即将在t个单位时间内完全石化，现在他对往事无限怀念，希望尽可能多的想起重要的人。

威廉有n个重要的人，而每个单位时间里他同时只能想一个人。

在此时此刻，回想第i个重要的人有关的事情都要消耗p[i]的时间，且只有时间p[i]完全经过才算确实回想起这个人。

威廉该按什么顺序回想，才能尽可能多的回顾和重要的人经历的事情呢？

输入输出格式

输入格式

第一行，包含两个正整数t,n。

接下来n行，每行包含一个字符串和一个正整数p[i]。其中字符串表示第i个重要的人的姓名。

输出格式

输出按最佳回想顺序能想起的人数。

输入输出样例

输入样例#1： 

1
2
3
4
5 3
Ri-ria 3
Naiguranto 5
Arumaria 2

输出样例#1： 

1
2

输入样例#2： 

1
2
3
4
5
6
10 5
Chtholly 2
Nephren 5
Ithea 3
Rhantolk 6
Lakhesh 4

输出样例#2： 

1
3

说明

每个字符串均不超过50个字符。

对于100%的数据，1<=t<=10000000,1<=n<=500000,1<=p[i]<=1000。

通过题目中描述，可知姓名是无用参数，不需保存处理；且仅有时间一种属性，可定性为dp的特例：贪心。当然用dp做也可以得出正解。

贪心做法：

sort之后从小到大开始算。

dp做法：

同背包问题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<algorithm>
using namespace std;
char s[50];
int a[500000],sum=0;
int main()
{
  int t,n,i,j;
  scanf("%d%d",&t,&n);
  for(i=0;i<n;i++) scanf("%s %d",s,&a[i]);
  sort(a,a+n);
  for(i=0;i<n;i++)
  {
      t-=a[i];
      if(t<0)
      {
          if(!i) printf("0");
          break;
      }
      sum++;
  }
  if(i) printf("%d",sum);
  return 0;
}
--It's the end.Thanks for your read.--