网络建站免费网址个人开发app去哪里接广告

Description

菱菱平时生活非常勤俭，从来只吃外卖不吃食堂。某日，好心的菱菱收养了一只流浪猫，但是猫咪对菱菱糟糕的伙食状况非常不满，屡次想要偷吃菱菱的鸟改善生活。于是菱菱想到放猫咪去食堂蹭饭，但是去食堂的路上有许多凶悍的野狗巡逻把守，直接去恐怕有来无回，当然这也难不倒聪明的菱菱，菱菱给猫咪做了一个外面画着老虎的盒子。这样猫咪可以在野狗经过的时候趴下休息，用盒子把自己保护起来。待危险解除后继续前行。同时由于经过了充分的休息，可以获得一定的能量点数，猫咪可以选择进行一次长达数米的跳跃。现在菱菱想知道猫咪最少需要多长时间可以到达食堂。

开始时，猫咪在坐标 0 点出发，初始能量为 0 ，食堂的坐标为 D 米，猫咪的前进速度为 1 米/秒。每一秒，猫咪可以选择原地休息（能量点加1）或前进 1 米或进行一次跳跃（前进 K 米，消耗 K−1 点能量，当然前提是当前拥有至少 K−1 点能量）。每一只野狗也在开始时同时出现，其属性包括出现时的坐标，前进速度，视野范围（可以同时向前和向后看）。每只野狗的前进方向都是坐标轴负方向。猫咪必须完全在狗的视野范围之外才能行动。

注意，判断在 x 位置的猫，前进 t 米，是否会被位置为 y ，速度为 a ，视野为 b 的狗发现的依据是[x; x + t]与[y−a−b; y + b] 的交是否为空集。

Input

测试文件包含多组数据。

每组数据第一行有两个整数，分别表示食堂的位置D(1≤D≤10000) 野狗的个数n(0≤n≤2,000)。

接下来有n 行，每行有三个整数，表示一只野狗的出现位置，前进速度，视野范围。保证野狗出现的位置小于2D。文件以一行两个 -1 表示结束。

Output

对于每组数据，输出一个整数t，表示猫咪到达食堂的时间。

Sample Input

10 3
18 2 1
3 2 1
8 1 2-1 -1

Sample Output

11

稍作分析：
简单题，但这道题当时我没有想出来，甚至考试结束看过解题依旧没有通过...最后还是经学长指点才勉强通过，由此可见....。
引用解题上的方法，这道题单纯模拟即可，能跳则跳。个人感觉时间卡的蛮紧，注意：已经路过的野狗及时要删掉，之后无需判断；
猫咪能够前行的最大距离为min(该点离最近的野狗视线前沿-1，魔力值+1，离食堂的距离），如果该点离最近的野狗视线前沿-1
为非正数，必须原地休整。

上代码：

#include <cstdio>
#include <malloc.h>
#define min(a,b) (a<b)?a:b
#define INF 0x3f3f3f3f
#define len (struct obj*)malloc(sizeof(struct obj)) 
struct obj{    
    int y,a,b;    
    struct obj*next;
}; 
int main(){
    int i,d,n,x,m,b,time;
    struct obj*head;
    struct obj*til;
    struct obj*tp;
    struct obj*p;
    while(scanf("%d %d",&d,&n)!=EOF&&(d!=-1||n!=-1)){
        head=len;
        til=head;
        til->next=NULL;
        for (i=1;i<=n;i++){
            til->next=len;
            til=til->next;
            til->next=NULL;
            scanf("%d %d %d",&til->y,&til->a,&til->b);
        }
        x=m=time=0;
        while(x<d){
            tp=head;
            while(tp->next!=NULL){
                if (x>tp->next->y+tp->next->b){
                    p=tp->next->next;
                    free(tp->next);
                    tp->next=p;
                }
                else tp=tp->next;
            }
            tp=head->next;
            b=INF;
            while(tp!=NULL){
                b=min(b,tp->y-tp->b-tp->a-x);
                tp=tp->next;
            }
            b--;
            b=min(b,d-x);
            if (b<0)b=0;
            b=min(b,m+1);
            m+=(-b+1);
            x+=b;
            tp=head->next;
            while(tp!=NULL){
                tp->y-=tp->a;
                tp=tp->next;
            }
            time++;
        }
        printf("%d\n",time);
    }
    return 0;
}