中级光能
https://ke.codingtang.com/#/problem/problemSub?id=1803
我的代码（超时80分）
#include <iostream>
using namespace std;
int d, n, ti, ans;
int a[1111][1111];
int b[1111][1111];
int maxx, minx = 11111111, maxy, miny = 11111111;
int sum(int x, int y) {
int cnt = 0;
for (int i = x - d; i <= x + d; i ++) {
for (int j = y - d; j <= y + d; j ++) {
cnt += a[i][j];
}
}
return cnt;
}
void flag(int x, int y) {
for (int i = x - d; i <= x + d; i ++) {
for (int j = y - d; j <= y + d; j ++) {
b[i][j] = 1;
}
}
}
int main() {
cin >> d >> n;
for (int i = 1; i <= n; i ++) {
int x, y, z;
cin >> x >> y >> z;
a[x][y] = z;
flag(x, y);
maxx = max(maxx, x);
maxy = max(maxy, y);
minx = min(minx, x);
miny = min(miny, y);
}
for (int i = max(minx - d, 0 + d); i <= min(maxx + d, 1024 - d); i ++) {
for (int j = max(miny - d, 0 + d); j <= min(maxx + d, 1024 - d); j ++) {
if (b[i][j] == 0) {
continue;
}
int x = sum(i, j);
if (x > ans) {
ans = x;
ti = 1;
} else if (x == ans) {
ti ++;
}
}
}
cout << ti << " " << ans;
return 0;
}
不知道怎么写才不会超时。本人菜鸟一枚，希望各位大佬指教！谢谢！
高级启示者
同上
新手天翼
挖坟喽！
新手光能
for(i=1;i<=n;i++){
cin>>x>>y>>l;
for(j=-m;j<=m;j++){
if(x+j>=0&&x+j<1025)
for(k=-m;k<=m;k++){
if(k+y>=0&&k+y<1025){
a[x+j][k+y]+=l;
}
}
}
}
emmm……我的核心，拿去参考一下吧
是一道枚举题，主要画个图看一下。
张欣悦在2021-07-10 13:18:21追加了内容
话说有帮助的话豆豆给我吧
张欣悦在2021-07-10 13:19:30追加了内容
有帮助吗？采纳一下？
缔造者之神
可以加上火车头，火车头可以加快200-300ms。
修练者
我就是菜鸟，这么简单的题目还用求助
新手天翼
应该遍历垃圾，不是遍历路口
资深守护
可以遍历路口，但要用二维数组前缀和维护
资深守护
大佬，能把题目发下吗？我不是酷町堂的。
初级光能
1、冲击波是以正方形方式扩散的（如果炸弹在（x,y）处，它能够炸到左至x-d处，右至x+d处，上至y+d处，下至y-d处）
2、城市的布局为严格的 1024 * 1024 的网格状，只有一枚炸弹，找到合适的投放地点，使得一次清除的垃圾总量最多
求：能清理垃圾最多的投放点数目，以及能够清除的垃圾总量
思路1：
定义一个数组a[1100][1100]记录每个点能炸掉多少垃圾
先输入每个垃圾的位置和数量x[i],y[i],t[i]
枚举网格中的每个点(i,j) (i:0~1024 j:0~1024)
枚举n处垃圾：
如果某处垃圾能被炸到（处在(i,j)点为中心的正方形范围内就能被炸到) ,就把它的垃圾数量统计到a[i][j]中
但是这个思路会超时， 首先双重循环枚举每个点，要循环1025*1025次，再枚举n处垃圾（n<=1000），那么1025*1025*1000肯定会超时的。
思路2：
在网格中一个点的周围街区有的有垃圾，有的没垃圾，计算的时候只有有垃圾的点会对结果产生影响，没垃圾的点不需要加到结果中去
所以我们可以反过来考虑，只考虑需要对有垃圾的点周围的街区加上垃圾数量
这样就是对于n处垃圾：
枚举以第i处垃圾为中心的正方形范围内所有点，如果在这些点安放炸弹都能炸到该处垃圾
（正方形下边界：x[i]-d ，上边界：x[i]+d ，左边界： y[i]-d ，右边界：y[i]+d ）
所以用一个二维数组记录每个点能炸到的垃圾数量的话，那么数组中这些点的元素数值都要相应地加上该处垃圾数量
初级天翼
不会
高级光能
大佬我不会，看我这个小渣渣的份上，采纳我吧
初级天翼
大佬，这一题我真的不会啊！！！
