Interview street上的一题求助# JobHunting - 待字闺中
f*i
1 楼
Problem solving (40 Points)
https://www.interviewstreet.com/challenges/dashboard/#problem/4ec82f33c6217
There are N problems numbered 1..N which you need to complete. You've
arranged the problems in increasing difficulty order, and the ith problem
has estimated difficulty level i. You have also assigned a rating vi to each
problem. Problems with similar vi values are similar in nature. On each day
, you will choose a subset of the problems and solve them. You've decided
that each subsequent problem solved on the day should be tougher than the
previous problem you solved on that day. Also, to not make it boring,
consecutive problems you solve should differ in their vi rating by at least
K. What is the least number of days in which you can solve all problems?
Input:
The first line contains the number of test cases T. T test cases follow.
Each case contains an integer N and K on the first line, followed by
integers v1,...,vn on the second line.
Output:
Output T lines, one for each test case, containing the minimum number of
days in which all problems can be solved.
Constraints:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000
------------------------------------------
Sample Input:
2
3 2
5 4 7
5 1
5 3 4 5 6
Sample Output:
2
1
Explanation:
For the first example, you can solve the problems with rating 5 and 7 on the
first day and the problem with rating 4 on the next day. Note that the
problems with rating 5 and 4 cannot be completed consecutively because the
ratings should differ by at least K (which is 2). Also, the problems cannot
be completed in order 5,7,4 in one day because the problems solved on a day
should be in increasing difficulty level.
For the second example, all problems can be solved on the same day.
===========================================================
一开始我觉得这题目很简单，只要greedy比较前后两个就可以了，后来发现不是这样。
当different是73的时候，对于
399 831 64 348 951 31 574 715 60 523 48 925 83 436 233 205 955 444 899 487
641 279 160 263 263 684 42 849 724 325 273 123 155 336 822 458 366 748 172
777 270 219 702 704 654 934 908 960 729 807 798 721 85 309 335 699 992 377
899 716 53 172 190 560 507 11 17 225 110 540 1 379 110 54 82 115 339 990 427
68 148 224 788 232 533 123 282 876 851 180 591 255 351 132 814 858 495 182
82 604 721 434 983 182 488 416 297 826 405 723 893 552 298 33 135 182 507
416 58 709 596 1000 963 298 484 777 155 978 310 588 933 383 22 267 564 861
683 212 686 87 286 931 991 584 315 477 117 821 893 526 529 840 526 491 137
361 619 644 338 929 583 622 311 956 889 226 816 571 438 854 9 723 784 351
658 98 828 127 270 72 652 150 911 529
输出结果应该是 4。
当different是 718 的时候，对于
31 94 575 127 594 487 254 544 75 815 714 180 378 763 776 89 920 711 733 295
18 347 236 138 692 154 944 574 329 926 292 711 19 218 837 964 56 91 859 131
905 572 662 634 686 790 74 605 852 806 251 869 504 486 7 196 640 950 121 968
227 764 678 597 982 866 561 37 956 771 519 212 343 533 197 380 322 271 985
173 428 235 41
输出结果是 43
https://www.interviewstreet.com/challenges/dashboard/#problem/4ec82f33c6217
There are N problems numbered 1..N which you need to complete. You've
arranged the problems in increasing difficulty order, and the ith problem
has estimated difficulty level i. You have also assigned a rating vi to each
problem. Problems with similar vi values are similar in nature. On each day
, you will choose a subset of the problems and solve them. You've decided
that each subsequent problem solved on the day should be tougher than the
previous problem you solved on that day. Also, to not make it boring,
consecutive problems you solve should differ in their vi rating by at least
K. What is the least number of days in which you can solve all problems?
Input:
The first line contains the number of test cases T. T test cases follow.
Each case contains an integer N and K on the first line, followed by
integers v1,...,vn on the second line.
Output:
Output T lines, one for each test case, containing the minimum number of
days in which all problems can be solved.
Constraints:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000
------------------------------------------
Sample Input:
2
3 2
5 4 7
5 1
5 3 4 5 6
Sample Output:
2
1
Explanation:
For the first example, you can solve the problems with rating 5 and 7 on the
first day and the problem with rating 4 on the next day. Note that the
problems with rating 5 and 4 cannot be completed consecutively because the
ratings should differ by at least K (which is 2). Also, the problems cannot
be completed in order 5,7,4 in one day because the problems solved on a day
should be in increasing difficulty level.
For the second example, all problems can be solved on the same day.
===========================================================
一开始我觉得这题目很简单，只要greedy比较前后两个就可以了，后来发现不是这样。
当different是73的时候，对于
399 831 64 348 951 31 574 715 60 523 48 925 83 436 233 205 955 444 899 487
641 279 160 263 263 684 42 849 724 325 273 123 155 336 822 458 366 748 172
777 270 219 702 704 654 934 908 960 729 807 798 721 85 309 335 699 992 377
899 716 53 172 190 560 507 11 17 225 110 540 1 379 110 54 82 115 339 990 427
68 148 224 788 232 533 123 282 876 851 180 591 255 351 132 814 858 495 182
82 604 721 434 983 182 488 416 297 826 405 723 893 552 298 33 135 182 507
416 58 709 596 1000 963 298 484 777 155 978 310 588 933 383 22 267 564 861
683 212 686 87 286 931 991 584 315 477 117 821 893 526 529 840 526 491 137
361 619 644 338 929 583 622 311 956 889 226 816 571 438 854 9 723 784 351
658 98 828 127 270 72 652 150 911 529
输出结果应该是 4。
当different是 718 的时候，对于
31 94 575 127 594 487 254 544 75 815 714 180 378 763 776 89 920 711 733 295
18 347 236 138 692 154 944 574 329 926 292 711 19 218 837 964 56 91 859 131
905 572 662 634 686 790 74 605 852 806 251 869 504 486 7 196 640 950 121 968
227 764 678 597 982 866 561 37 956 771 519 212 343 533 197 380 322 271 985
173 428 235 41
输出结果是 43