2015-09-06
问题大意：萨鲁曼白想要让他的军队从sengard到Helm’s Deep，为了跟踪他的军队，他在军队中放置了魔法石（军队是一条线），魔法石可以看到前后距离为R的距离，为了让魔法石发挥最大的效益，魔法石戴在军人的身上，问你怎么才能使用最少的石头
问题很清晰，思路也很清晰，这道题挺典型的，就是贪心算法，
很容易想到的就是我们只用在距离内找到最后的点（人），然后把魔法石放到其上面就行了，然后依次类推，最后就可以达到最少的数量
具体可以以2R为一次循环，在前R的区间内我们找到要标记的点，然后移动R的距离，再来一次就可以了。很容易想到，画个图就可以了
#include <stdio.h>
#include <stdlib.h>
#define SWAP(a,b) { (*a)^=(*b);(*b)^=(*a);(*a)^=(*b);}
#define CUTOFF 20 typedef int Position; void Quick_Sort(Position *, Position, Position);
int Get_Pivot(Position, Position, Position,Position *);
void Insertion_Sort(Position *, Position, Position);
void Search(Position *, const int, const int); int main(void)
{
int R, T, i;
Position *Troops = NULL;
while (~scanf("%d%d", &R, &T)
&& R >=
&& T >= )
{
Troops = (Position *)malloc(sizeof(int)*T);
for (i = ; i < T; i++)
scanf("%d", &Troops[i]);
Quick_Sort(Troops, , T - );
Search(Troops, R, T);
free(Troops);
}
} int Get_Pivot(Position left, Position right, Position mid,Position *A)
{
if (A[left] > A[mid]) SWAP(&A[left], &A[mid]);
if (A[left] > A[right]) SWAP(&A[left], &A[right]);
if (A[mid] > A[right]) SWAP(&A[mid], &A[right]); SWAP(&A[mid], &A[right]);//隐藏枢纽元
return A[right];
} void Quick_Sort(Position *A, Position left, Position right)
{
Position i = left, j = right , mid = (left + right) / ;
int pivot;
if (right - left > CUTOFF)
{
pivot = Get_Pivot(left, right, mid, A);
while ()
{
while (A[--j] > pivot);
while (A[++i] < pivot);
if (i < j)
SWAP(&A[i], &A[j])
else break;
}
SWAP(&A[i], &A[right]);//重新显示枢纽元
Quick_Sort(A, left, i - );
Quick_Sort(A, i + , right);
}
else Insertion_Sort(A, left, right);//转插入排序
} void Insertion_Sort(Position *A, Position left, Position right)
{
Position i, j;
int tmp;
for (i = left; i <= right; i++)
{
tmp = A[i];
for (j = i; j > left && A[j - ] > tmp; j--)
A[j] = A[j - ];
A[j] = tmp;
}
} void Search(Position *Troops, const int R, const int T)
{
Position i = , mark, s, ans = ;
for (; i < T;)
{
s = Troops[i++];//获得区间的最左点
for (; i < T && Troops[i] <= s + R; i++);
mark = Troops[i - ];//在R内的最右点，标记
for (; i < T && Troops[i] <= mark + R; i++);
ans++;
}
printf("%d\n", ans);
}