【t042】炮击坦克

Time Limit: 1 second
Memory Limit: 128 MB

【问题描述】

在一个坐标轴上，有M辆坦克，第i辆坦克在时刻0处于pos[i]（pos[i]>0），speed[i]个单位，在时刻k就处于pos[i]+speed[i]*k。
原点上有一炮台。炮台有N颗炮弹，在时刻0开始就可以发射炮弹，而且发射的顺序是你来确定的，每次只能发射一颗，一颗炮弹只能
用一次。每个炮弹都有一个休息时间rest[i]，如果在某次发射了第i颗炮弹，要间隔rest[i]后才能在发射。一颗炮弹只能消灭
范围D(0到D)内的一辆坦克。
最多能消灭多少辆坦克？
【输入格式】

第一行：N，M，D(N,M≤1000)
接下来N行：rest
接下来M行：pos, speed
全部都是longint内的正整数。
【输出格式】

输出最多能消灭坦克数量。

Sample Input

3 3 3
3
2
1
4 1
1 1
2 1

Sample Output

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t042

【题解】

因为每枚炮弹的攻击范围是固定的;而坦克是越来越远的;
则肯定先用休息时间短的炮弹;
确定用哪个炮弹之后;其实第i次发射的炮弹(休息时间从小到大数第i个)能够攻击到的坦克就固定了;
且i越大;那枚炮弹能够攻击到的坦克就越少;(因为坦克越来越远);
这样我们先处理出第i枚炮弹的能够攻击到哪些坦克;
从第n枚炮弹开始,倒序枚举,看看第n枚炮弹能够攻击到哪些坦克;
随便攻击一个就好;
然后是第n-1枚炮弹,看看第n-1枚炮弹能够攻击到哪些坦克(且之前没有被攻击到)那就攻击它;
….
然后计数攻击了多少个坦克就好;
第i个炮弹能够攻击到的坦克,第i-1个炮弹肯定也能攻击到;
因为i越大,能够攻击到的坦克越来越少;
所以才这样,先选那些靠后都能攻击到的坦克,这样才能尽可能地为其他靠后就不能攻击到的坦克腾出炮弹;

【完整代码】

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long

const int MAXN = 1e3+10;

struct abc
{
    LL pos,speed;
};

LL rest[MAXN],d;
int n,m,cnt = 0;
abc a[MAXN];
bool bo[MAXN],can[MAXN][MAXN];

int main()
{
    //freopen("F:\rush.txt","r",stdin);
    scanf("%d%d%I64d",&n,&m,&d);
    for (int i = 1;i <= n;i++)
        scanf("%I64d",&rest[i]);
    sort(rest+1,rest+1+n);
    for (int i = 1;i <= m;i++)
        scanf("%I64d%I64d",&a[i].pos,&a[i].speed);
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= m;j++)
            if (a[j].pos<=d)
                can[i][j] = true;
        for (int j = 1;j <= m;j++)
            a[j].pos+=rest[i]*a[j].speed;
    }
    for (int i = n;i>=1;i--)
    {
        for (int j = 1;j <= m;j++)
            if (!bo[j] && can[i][j])
            {
                bo[j] = true;
                cnt++;
                break;
            }
    }
    printf("%d
",cnt);
    return 0;
}