【POJ 3069】(2586见下)
原题在此：http://poj.org/problem?id=3069
题目大意：
一个直线上有N个点。点i的距离是Xi。从这些点中选取若干个加上标记。要求：对于每个点，与其距离为R的范围内必有做标记的点（包括自身）。求至少标记多少点才能满足要求。
输入：N， R，以及N个点各自距原点的距离（①不一定按照顺序，故需要排序 ②可以重叠）。
输出：被标记的点的最少个数。
解题思路：
从最左边开始看，在距离为R的范围内，被标记的点一定在第一个点的右侧（或是自身）。为了使整体标记的点最少，故应当将R范围内最右边（如果没有则标记自身）的点进行标记。即尽可能的向右辐射。
同样的，对于被标记的点，其右边超出范围Ｒ的第一个点重复上述操作，直到辐射到所有的点。
代码：
#include<iostream>
#include<algorithm>
using namespace std; int main() {
int R;//范围
int N;//点的个数
int x[];//记录位置
while ()
{
cin >> R >> N;
if (R == - && N == -)//退出
break;
for (int i = ; i < N; i++)
{
cin >> x[i];
}
sort(x, x + N);//将里面的位置排序
int n = , ans = ; while (n<N)
{
int s = x[n++];//s是没有被辐射到的最左边的那个点 while (n < N&&x[n] <= s + R)
n++;//遍历到超出s的R范围的第一个点
int p = x[n - ];//p是新标记上的点 while (n < N&&x[n] <= p + R)
n++;//前往新标记的点的最远方
ans++;
}
cout << ans << endl;
} return ;
}
【POJ 2586】
原题在此：http://poj.org/problem?id=306
题目大意：
讲的是一个奇怪的公司，它每个月要不然盈利S要不然亏损d。更有意思的是这家公司的数据出现问题，只记得自己在这一年12个月里面，任何连续五个月里面总体都是亏损的（里面可能有亏损有盈利，但和是亏损）。问有可能的最大盈利额是多少（要求输出）。
输入：s,d；
输出：如果盈利输出有可能的最大盈利额，如果亏损输出 Deficit。
解题思路：
和3069一样呀，从最左边开始，每五个一组，额不过12个月只能两组单两个。这样让有亏损的月份在小组里尽量往后排，尽力向又辐射！
如上图：红越深的地方优先选定为亏损的月份，这样辐射范围最广
下面呢，就要确定有多少个亏损月份了，知道了s和d确定亏损月份数量不是难事，注意下，如果s≥4*d的时候，必然是12个月全部亏损。另外一点，当3*d<=2*s且s<4 * d的时候，刚才一直没考虑11,12月也要开始考虑了，此时11和12月必有一个为亏损月，要不然选择最后5个月就不符合题意了。
代码：
#include<iostream>
#include<algorithm>
using namespace std; int profit(int s, int d)
{
if (d > * s)
return -*d+*s;
else if ( * d > * s)
return -*d+*s;
else if ( * d > * s)
return -*d+*s;
else if ( * d > s)
return -*d+*s;
else
return -;
} int main() {
int s, d;
while (cin >> s >> d)
{
int sum = profit(s, d);
if (sum >= )
{
cout << sum << endl;
}
else {
cout << "Deficit" << endl;
}
}
return ;
}