奶牛贝茜设计了一款她认为必火的游戏:愤怒的奶牛。
游戏设定(她坚信这是她的原创)是玩家用一个d弓将一头奶牛射向一个数轴,数轴的不同位置上分布着一些干草捆。
奶牛以足够的力量砸向某个干草捆,并使得该干草捆发生爆炸,爆炸可能会不断引起连锁反应,导致更多的干草捆发生爆炸。
目标是用一头奶牛引起的连锁反应引爆尽可能多的干草捆。
共有 N 个干草捆位于数轴中的不同整数位置,其坐标依次为 x1,x2,…,xN。
如果将奶牛射向位于位置 x 的干草捆,则该干草捆发生爆炸,爆炸半径为 1,爆炸将吞噬 1 单位距离内的所有干草捆。
然后这些干草捆(全部同时)发生爆炸,每个干草捆的爆炸半径为 2。
二次爆炸中吞噬的所有尚未爆炸的干草捆也(全部同时)发生爆炸,爆炸半径为 3。
也就是说,在 t 时刻爆炸的干草捆的爆炸半径为 t,其爆炸波及的干草捆在 t+1 时刻也会爆炸,爆炸半径为 t+1,以此类推。
请确定,通过合理选择奶牛射向的干草捆,能够引爆的干草捆最大数量。
输入格式
第一行包含整数 N。
接下来 N 行包含 x1,…,xN。
输出格式
输出能够引爆的干草捆的最大数量。
数据范围
1≤N≤100, 0≤xi≤ 1 0 9 10^9 109
输入样例:
6 8 5 6 13 3 4
输出样例:
5
样例解释
将奶牛射向位于位置 5 的干草捆,产生半径为 1 的爆炸。
爆炸吞噬位置 4 和 6 处的干草捆,引发半径为 2 的二次爆炸。
二次爆炸吞噬位置 3 和 8 处的干草捆,引发半径为 3 的三次爆炸。
位置 13 的干草捆无法被引爆。
完整代码暴力引爆每一个点
取L,R两个左右边界
每次向两边延伸
以L为例子,每次找一个大于等于 *L + t 的点,如果这点是新点,则更新L,否则就是最远点
取两端边界距离为答案
#include代码理解 关于lower_bound 和 upper_bound的使用using namespace std; int n; int ans; int main() { cin >> n; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); for(auto i = a.begin(); i != a.end(); i++) { auto l = i, r = i; int tl = 1, tr = 1; while(lower_bound(a.begin(), l, *l - tl) != l) l = lower_bound(a.begin(), l, *l - tl++); while(--upper_bound(r, a.end(), *r + tr) != r) r = --upper_bound(r, a.end(), *r + tr++); ans = max(ans, (int)(r - l + 1)); } cout << ans << endl; return 0; }
这两个函数均为二分查找, 所以 原数组必须有序
lower_bound 返回 第一个大于等于 x 的地址
upper_bound 返回 第一个大于 x 的地址
示例
#includeusing namespace std; int n; int ans; int main() { cin >> n; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); auto x = lower_bound(a.begin(), a.end(), 3); printf("lower_bound:%dn", x); x = upper_bound(a.begin(), a.end(), 3); printf("upper_bound:%dn", x); return 0; }
#includeusing namespace std; int n; int ans; int main() { cin >> n; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); auto x = lower_bound(a.begin(), a.end(), 3); printf("lower_bound:%dn", x); x = upper_bound(a.begin(), a.end(), 2);//这里改成了2 printf("upper_bound:%dn", x); return 0; }
如果我们需要的是 小于等于 x 的最后一个数
比如 该样例中 3 4 5 6 8 13
我想要知道小于等于8的最后一个数 也就是 8
那么,我们可以先用 upper_bound 找到大于 8 的第一个数 也就是 13
然后再进行自减运算 即 --upper_bound 就能找到小于等于8的最后一个数
示例
#include方法二——BFSusing namespace std; int n; int ans; int main() { cin >> n; vector a(n); for(int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); auto x = upper_bound(a.begin(), a.end(), 8); printf("x's address:%dn", x); printf("x:%dn", *x); auto y = --upper_bound(a.begin(), a.end(), 8); printf("y's address:%dn", y); printf("y:%dn",*y); return 0; }
#includeusing namespace std; const int N = 110; int a[N]; int n; unordered_map mp; int ans; int main() { cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; mp[a[i]] = -1; } for(int i = 0; i < n; i++) { auto st = mp; st[a[i]] = 1; int num = 0; queue q; q.push(a[i]); while(!q.empty()) { int t = q.front(); q.pop(); num++; for(int i = -st[t]; i <= st[t]; i++) { if(st[i + t] == -1) { q.push(i + t); st[i + t] = st[t] + 1; } } } ans = max(ans, num); } cout << ans << endl; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)