Saruman's Army

时间限制：1s

内存限制：128M

白袍巫师萨鲁曼需要指挥他的军队前往圣盔谷. 士兵们在行军过程中的队形是长长的一列, 萨鲁曼需要在士兵中选出若干名任命为传令官, 传令官只能将命令传到与自己距离不超过R的范围 (如果R=0,则命令只能传到和自己位置相同的士兵). 萨鲁曼需要保证每位士兵都能听到命令, 并且任命的传令官越少越好. 输入士兵人数n和每位士兵的位置xi, 输出所需的传令官的最少人数.

输入格式

输入第一行包含两个正整数R和n分别代表半径和军队人数

输入第二行包含n个正整数x1 x2 x3......xn 代表每位士兵的位置.

输出格式

输出所需的传令官的最少人数.

#include <bits/stdc++.h>
using namespace std;
int r,n,soldier[1005],maxn,now=1,bao,wei,ans;
int main()
{
	cin>>r>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>soldier[i];
	}
	sort(soldier+1,soldier+n+1);
	while (!(wei>=soldier[n]))
	{
		maxn=-1;
		for (int i=1;i<=n;i++)
		{
			if (soldier[i]>wei)
			{
				bao=i;
				break;
			}
		}
		while (1)
		{
			if (now>n)
			{
				break;
			}
			if (soldier[now]-r<=soldier[bao])
			{
				maxn=max(maxn,soldier[now]+r);
				now++;
			}
			else
			{
				break;
			}
		}
		wei=maxn;
		ans++;
	}
	cout<<ans;
	return 0;
}

是个区间贪心

WA 是这个点

7 777

429 46 72 111 7 499 864 465 7 508 40 575 766 237 230 332 894 413 468 890 300 508 468 894 196 746 300 9 40 111 9 571 468 211 998 567 103 40 300 494 214 797 413 103 7 216 634 998 293 489 62 43 675 842 540 465 614 549 619 33 734 960 609 72 696 429 878 332 260 11 299 578 911 640 797 577 494 319 72 864 864 33 198 609 128 304 642 279 9 504 300 11 787 974 499 62 434 15 504 797 489 332 893 648 597 429 388 248 0 9 577 843 807 9 49 275 403 345 254 103 214 766 988 300 85 603 494 642 734 603 549 29 634 603 504 597 103 982 578 9 198 549 208 960 878 567 603 577 234 673 504 571 103 254 35 504 300 144 863 842 818 767 413 16 93 603 309 49 894 25 567 7 304 673 62 152 0 619 300 770 214 293 549 960 299 568 943 0 843 429 33 103 300 543 413 974 37 429 894 982 494 152 603 863 863 833 212 152 911 111 818 614 911 614 37 0 508 248 982 766 974 787 332 474 465 25 770 474 575 597 499 237 489 111 216 403 766 864 508 807 212 304 403 767 974 300 25 982 669 603 26 508 787 634 818 787 504 93 609 673 11 577 787 144 807 982 465 230 234 152 734 648 279 332 474 37 883 9 499 208 549 603 293 911 578 597 540 960 770 26 609 807 640 818 998 878 16 504 988 797 211 597 93 93 403 982 642 93 25 214 144 208 578 211 642 669 807 578 648 198 403 345 787 40 863 125 675 15 787 388 111 864 640 543 818 254 878 9 214 508 93 508 25 998 16 911 807 571 300 638 37 974 638 16 619 144 640 578 128 863 40 214 499 571 300 766 807 613 125 198 37 998 508 960 638 9 890 214 25 332 72 864 248 766 230 734 499 29 309 609 29 766 211 988 128 603 833 833 429 982 293 746 429 49 144 543 216 254 468 568 128 696 474 787 85 614 62 465 797 642 388 571 144 234 49 16 504 494 208 974 62 211 345 275 568 974 575 299 746 144 494 46 807 499 640 275 499 40 767 413 770 26 734 863 787 125 638 575 216 309 208 388 214 230 208 883 642 619 465 465 675 549 29 638 770 797 807 299 943 842 504 504 766 960 15 613 465 767 843 648 196 9 125 230 673 734 37 540 434 212 770 540 0 571 833 474 648 675 597 508 770 842 111 890 40 883 237 842 125 982 696 878 575 998 878 26 642 543 33 613 237 571 675 894 111 11 787 237 9 883 504 638 597 578 842 974 982 696 960 260 279 567 540 237 614 144 49 634 293 673 300 864 345 230 345 49 237 960 25 864 299 0 634 499 319 767 894 29 72 609 230 648 474 911 7 275 35 293 37 474 894 7 49 388 734 214 85 211 577 9 29 254 508 543 275 638 597 300 319 299 103 911 499 988 998 309 603 767 413 890 319 943 614 894 960 614 640 696 807 568 309 568 508 960 62 696 216 128 642 988 144 260 237 46 46 332 144 494 864 878 864 196 640 468 152 103 309 638 37 93 833 0 7 468 766 214 234 982 474 577 960 543 403 696 807 0 7 212 43 332 634 619 208 634 489 103 943 211 468 299 571 567 696 988 332 575 675 474 40 893 260 998 640 260 982 46 237 254 125 196 11 299 619 577 638 669 309 943 237 494 275 128 988 9 33 72 613 894 609 603 0 345 468 787 300 214 49 675 893 319 468 26 575 474 37 111 571 49 16 575 212 15 279 49 998 504 198 234 833 248 634 893 208 843 669 833 300 293 603 198 642 254 807 230 332 103 211 （CSDN的大神解法看不懂）