本文主要是介绍C/-d D - Saruman's Army，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
呀吧 可算是a掉了
补得题，可算是懂得题目是啥意思了，就是最少包含范围，在给定的数左右 r的范围内都是可以的覆盖的，
对于派出的兵，能够防守一个范围的，问最少守几个数
后来发现这其实也是一个贪心算法的例题
Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range ofR units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.
The input test file will contain multiple cases. Each test case begins with a single line containing an integerR, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integern, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positionsx1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case withR = n = −1.
For each test case, print a single integer indicating the minimum number of palantirs needed.
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1
2 4
#include <iostream>
#include<algorithm>using namespace std;
int army[1005];
int main()
{int r,n;while(cin>>r>>n&&(r!=-1&&n!=-1)){ int num=0;for(int i=0;i<n;i++)cin>>army[i];sort(army,army+n);for(int i=0;i<n;){int sum=0;int mid=i;int left=i;while(i<n){if(army[mid]-army[left]>r)break;if(army[i]-army[mid]<=r){i++;}else{mid++;}}num++;}cout <<num<< endl;}return 0;
}
贪心算法：
从最左方开始，寻找范围内第一个节点，即驻扎点，标记后，再寻找右方新的第一个超出范围的点，然后重新开始
#include <iostream>
#include<algorithm>using namespace std;
int army[1005];
int r,n;
void solve()
{int i=0,ans=0;while(i<n){int s=army[i++];//第一个点的坐标，++后进入下一个点,其实等价于 s=army[i];i=i+1;while(i<n&&army[i]<=s+r) i++;int p=army[i-1];//此处不能忘了减一，因为此时的i已经超出了范围，需要减一while(i<n&&army[i]<=p+r) i++;ans++;}cout<<ans<<endl;
}
int main()
{while(cin>>r>>n&&(r!=-1&&n!=-1)){ int num=0;for(int i=0;i<n;i++)cin>>army[i];sort(army,army+n);solve();}return 0;
}
这篇关于C/-d D - Saruman's Army的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
