CodeForce 607A&&608C Chain Reaction

[题目传送门] ---------------> http://codeforces.com/problemset/problem/608/C

[题目]

  

There are n beacons located at distinct positions on a number line. The i-th beacon has position ai and power level bi. When the i-th beacon is activated, it destroys all beacons to its left (direction of decreasing coordinates) within distance bi inclusive. The beacon itself is not destroyed however. Saitama will activate the beacons one at a time from right to left. If a beacon is destroyed, it cannot be activated.

Saitama wants Genos to add a beacon strictly to the right of all the existing beacons, with any position and any power level, such that the least possible number of beacons are destroyed. Note that Genos‘s placement of the beacon means it will be the first beacon activated. Help Genos by finding the minimum number of beacons that could be destroyed.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100 000) — the initial number of beacons.

The i-th of next n lines contains two integers ai and bi (0 ≤ ai ≤ 1 000 000, 1 ≤ bi ≤ 1 000 000) — the position and power level of the i-th beacon respectively. No two beacons will have the same position, so ai ≠ aj if i ≠ j.

Output

Print a single integer — the minimum number of beacons that could be destroyed if exactly one beacon is added.

Sample test(s)

Input

41 93 16 17 4

Output

1

Input

71 12 13 14 15 16 17 1

Output

3

[思路]

DP + 二分

   读入灯塔数据,位置和能量到一个pair中然后按升序sort。

  dis[i] 代表 dis[i] 被点亮时,被摧毁的左边的灯塔的数量。最左边的灯塔能量不管是多少都没有摧毁的东西 所以 dis[0] = 0;

  接下来进行状态转移(for k = 1 ; k < n ; k++),对于第k个灯塔都从前一个 “没有被k灯点亮而摧毁的灯塔处” 进行转移,加上 点亮第k个灯塔所摧毁的灯塔数,如果发现第k个灯塔左边所有的灯塔都被摧毁了,则 dp[k] = k;

  分析得,题中要求加入一个最右边的灯塔,其实意思是让我们  “从一开始的序列中 直接从最右边开始去掉若干灯塔当作被摧毁 ” 然后剩下的序列继续进行点亮操作后算出被摧毁的灯塔数目。  求出所有可能的方案中的最小数量。

  枚举去掉最右边的0个灯塔,一个灯塔,两个灯塔。。。。t 个灯塔

  当去掉 t 个灯塔时, 被摧毁的灯塔总数就是 t + dis[n - 1 - t];

  找出最小即可。

[代码]

  

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 #define pos first
 7 #define power second
 8 #define MAX 100010
 9 #define PLL pair<int,int>
10 #define LL long long
11
12 LL dis[MAX];
13 PLL node[MAX];
14 LL min(LL a , LL b) {return a < b ? a : b;}
15
16 int main()
17 {
18     int n;
19     cin >> n;
20     dis[0] = 0;
21     ///////////////////
22     for(int i = 0 ; i < n ; i++)
23     {
24         cin >> node[i].pos >> node[i].power;
25     }
26     sort(node , node + n);
27     for(int i = 1 ; i < n ; i++)
28     {
29         int curpos = node[i].pos;
30         int curpower = node[i].power;
31         int in_pos = lower_bound(node , node + n , make_pair(node[i].pos - node[i].power,0)) - node;
32         if(in_pos > 0)
33         {
34             dis[i] = dis[in_pos - 1] + (i - in_pos);
35         }
36         else
37         {
38             dis[i] = i;
39         }
40     }
41     LL ans = n;
42     for(int i = 0 ; i < n ; i++)
43     {
44         dis[i] = dis[i] + (n - i - 1);
45         ans = min(dis[i] , ans);
46     }
47     cout << ans << endl;
48     return 0;
49
50 }
时间: 12-24

CodeForce 607A&&608C Chain Reaction的相关文章

Codeforces 607A - Chain Reaction - [DP+二分]

题目链接:https://codeforces.com/problemset/problem/607/A 题意: 有 $n$ 个塔排成一行,第 $i$ 个激光塔的位置为 $a_i$,伤害范围是 $b_i$,激活第 $i$ 个塔后,所有在这个塔左侧且距离小于等于 $b_i$ 的塔都会被摧毁,但该塔本身不会被摧毁. 现在会从右向左依次激活每个塔,如果一个塔被摧毁则无法被激活. 现在要在这 $n$ 个激光塔的右边再放一个塔,该塔的位置和威力是任意的.现在从这个新加入的塔开始从右到左依次激活每个塔,求最

2018省赛赛第一次训练题解和ac代码

第一次就去拉了点思维很神奇的CF题目 # Origin Title     A CodeForces 607A Chain Reaction     B CodeForces 385C Bear and Prime Numbers     C CodeForces 670D2 Magic Powder - 2     D CodeForces 360B Levko and Array     E CodeForces 68B Energy exchange     F CodeForces 24

HBV DNA level _data analysis

HBV 表明抗原阳性是HCC最重要风险因子 Seropositivity for the hepatitis B surface antigen (HBsAg) is one of the most important risk factors for hepatocellular carcinoma hbv e 抗原阳性会增加HCC风险 In our previous study, seropositivity for the hepatitis B e antigen (HBeAg) was

[转载]50个Demo展示HTML5无穷的魅力

Flash和HTML5的比较已经成为现在最热门的主题之一,我们不去争论哪个好哪个不好.和HTML5在很酷的动画和简单的游戏等方面一样,除非HTML5在未来几年有一些重大发展,否则Flash在富内容网页应用和游戏方面永远是不错的选择.下面收集了50个非常酷的HTML5应用实例来展示其无限潜力. 1. Tunneler 2. JuicyDrop 3. Magnetic 4. Trail 5. Sinuous 6. DDD 7. Harmony 8. Lines go all over the pla

肺炎-维基百科

http://en.wikipedia.org/wiki/Pneumonia the number of words: 3110word           count---------------------pneumoniae        18respiratory       17streptococcus      15aspiration        11pulmonary          9interstitial       9sputum             6infl

隐匿性乙肝病毒感染:一种秘密行动

Journal of Viral Hepatitis Occult Hepatitis B Virus Infection: A Covert Operation F. B. Hollinger, G. Sood Disclosures Summary and Introduction Summary Detection of occult hepatitis B requires assays of the highest sensitivity and specificity with a

BEAMing技术

数字PCR(digital polymerase chain reaction,dPCR)作为DNA定量的新技术,实现了单分子DNA绝对定量.dPCR是将单个DNA样品反应液分别进行数以百计的反应,并且每个反应分别进行扩增检测. 此技术在临床诊断.转基因成分定量.单细胞基因表达.环境微生物检测和下一代测序等方面的研究发挥了重要作用.BEAMing技术:结合了数字PCR以及流式技术,最早是由Bert Vogelstein提出.其方法是每一类DNA分子都会专一的与磁性珠相连接,然后DNA分子之间的差

bzoj4509【Usaco2016 Jan】Angry Cows

4509: [Usaco2016 Jan]Angry Cows Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 83  Solved: 38 [Submit][Status][Discuss] Description Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, whi

《黑客帝国》完全解析(转)

万事皆有始亦有终——<The Matrix>影评之终结篇  一.前言 从 Matrix I 到 Matrix III,整整四年,一对名叫沃卓斯基(导演加编剧)的兄弟给科幻电影带来一次史无前例的冲击,无论从思想上还是视觉效果上都超过了以往任何一部科幻电影,从来没有一部科幻电影能够创造这么多的 Fans 也没有任何一部科幻电影能像 Matrix 这样引发如此大规模的讨论——讨论剧情,讨论主题,讨论特效,讨论演员,笔者绝不敢自称 100% 的看懂了(我把看懂定义为“理解沃卓斯基兄弟眼中剧情和主题的原