题解 - Vijos

#include <cstdio>
int n,k,m;
int a[100005],b[100005],f[100005];
int main(){
    scanf("%d%d",&n,&k);
    for (int i=1;i<=k;++i) scanf("%d%d",&a[i],&b[i]);
    for (int i=n;i>=1;--i)
        if (a[k]!=i) f[i]=f[i+1]+1;
        else while (a[k]==i){
            f[i]=f[i]>=f[i+b[k]]?f[i]:f[i+b[k]];
            k--;
        }
    printf("%d",n-f[1]);
}

0
great马甲 LV 8 @ 15 年前

我不可以删排序，因为我用的是筒派！
0
lishunzhi LV 9 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

题意严重不清...

到底是最小时间还是最大时间还是最大零件个数????

且为什么不能用快排??????

稀里糊涂地得了几次10分.

又稀里糊涂地看了题解AC了..
0
syh173 LV 9 @ 15 年前

哪位牛解释一下为什么不能用快排？？？
0
honghaijie LV 9 @ 15 年前

数据量真大..
0
1oVe YoU疾风 LV 10 @ 15 年前

尼克的任务的改编版，虽然问题不一样但本质是一样的

前者求最大的空隙，该题求最小工作，n-f[1] 就OK乐
0
notblack LV 10 @ 15 年前

这题上次不就消失了么，怎么回光返照了？我是没兴趣做了。
0
huyuanming11 LV 10 @ 15 年前

......

做了VIJOS上这么多WS的题目，我已经养成看题解的习惯了......

好像不看题解总要WA几次...
0
hzk LV 8 @ 15 年前

草，不能快排。。
0
水莫世界 LV 9 @ 15 年前

排序后过不去吗？
0
LYK LV 9 @ 15 年前

竟然不要快排、、、

数据有没有问题？？？
0
fengye61yi LV 8 @ 15 年前

为什么+QSORT错了
0
新手上路 LV 8 @ 15 年前

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

103名......啊！！！！！！！！！
0
wwss LV 8 @ 15 年前

100名！O(∩_∩)O

Flag 　　Accepted

题号　　P1634

类型(?) 　　其它

通过　　100人

提交　　563次

通过率　　18%

难度　　1
0
code-geass LV 9 @ 15 年前

= =QSORT.............为什么不能过............

又为什么我将数组反过来也照样AC................
0
xiaoX LV 10 @ 15 年前

总司希望知道最少机器能生产多少个零件（也就是最少工作多少分钟）

仅一行，表示机器最多可能加工零件的时间。(SO EASY =.=);

so easy ，我根本连题目都看不懂的说。。。。。

最少多少零件？最少工作时间？最多工作时间？到底是哪个。。。
0
ltby LV 10 @ 15 年前

什么鸟题嘛，用快排有什么错！
0
我不是你 LV 8 @ 15 年前

事实证明不能快排
0
wgq LV 9 @ 15 年前

加上快排和不加快排有序不都一样吗？？？怎么不对？删了快排才行？
0
yuancf LV 8 @ 15 年前

流年、卜襟言阿、

我膜拜您。

以后在VJ上混就靠你了。