2015
04-16

# Phage War

Phage War is a little flash game. In this game, we want infect all cells by the transmission and breed of phages.
Originally, there is a cell infected by phages and this cell can breed a new phage every second. You should know that only the new born phages can inject other cells.

There are n cells around this cell, numbered from 1 to n. If there are Di phages reaching the i-th cell, the cell would be infected, and the phages journey will cost Ti seconds. To simplify it, we assume these phages will stay in this new cell and they can’t infect other cells. And the new cell cannot breed new phages and infect other cells.
Can you tell me how much time it costs to infect all cells at least?

In the first line there is an integer T (T <= 50), indicates the number of test cases.
In each case, the first line contains a integers N (1 <= N <= 10^5). Then there are N lines, each line contain two integers Di, Ti (1<=Di, Ti<=100).

In the first line there is an integer T (T <= 50), indicates the number of test cases.
In each case, the first line contains a integers N (1 <= N <= 10^5). Then there are N lines, each line contain two integers Di, Ti (1<=Di, Ti<=100).

2
2
2 1
5 6
2
1 11
3 10

Case 1: 11
Case 2: 14

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100004
struct node
{
int s,t;
}ans[N];
bool cmp(node a,node b)
{
if(a.t!=b.t)return a.t>b.t;
else a.s>b.s;
}
int main()
{
int t,c=0,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&ans[i].s,&ans[i].t);
}
sort(ans,ans+n,cmp);
int ans1=0,time=0;
for(int i =0;i<n;i++)
{
time+=ans[i].s;
ans1=max(time+ans[i].t,ans1);
}
printf("Case %d: %d\n",++c,ans1);
}
return 0;
}


（1）题目为什么要这样做。

首先分析一下题意。题目大意是有一个细胞，每分钟都产生一个噬菌体。这些噬菌体能够感人细胞。一个细胞被感染的时间是这样计算的。如果一个细胞被感染需要n噬菌体，并且这些细胞到达将被感染细胞时间是m，那么这个细胞被感染的时间就是m+n。题目求的是，所有的细胞被感染后所用的最短的时间。

这个题目需要做两步工作。第一是，排序。第二是，贪心。排序是贪心得以进行的前提。按照达到时间最大的排序，这样我们得到了一个最短的时间（想一想，到达时间最大的这个时间一定是小于等于所有细胞被感染的最短时间的，所以我们把这个时间最为最短时间来进行更新）。这个时间就是我们更新的基础。接下来的步骤就是更新时间。我们要做的就是按照排序后的结果，来判断时间是否需要更新。这样一步一步进行下去，每一步都得到的是最优的解，最后得到了整体最优解。这就是贪心。其实排序是一种贪心的策略。

这个题目排序工作想要达到的目的必需要想清楚了。这是理解这个题目的关键。

流程图：

（2）这个题目的解答还有没有改进的地方？

（3）还有其他的方法吗？

1. 你的理解应该是：即使主持人拿走一个箱子对结果没有影响。这样想，主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率，但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3