三个TLE求dalao教一下咋优化TLE求dalao教一下咋优化TLE

P1003 [NOIP2011 提高组] 铺地毯

~~标题可能爆炸了不要介意~~
by lizer @ 2018-11-18 22:38:22


来几个dalao指教指教啊...
by lizer @ 2018-11-18 22:38:48


```cpp for(i=n;i>=1;i--) if(x>=a[i] && x<=a[i]+c[i] && y>=b[i] && y<=b[i]+d[i]){ printf("%d",i); return 0; } ``` 这样(变量名不一样不要介意)
by 梧桐灯 @ 2018-11-18 22:39:53


@[光随影走](/space/show?uid=31193) emmm不~~是很~~明白...
by lizer @ 2018-11-18 22:44:56


@[liyize](/space/show?uid=111010) 就是判断一个地毯是否覆盖一个坐标只需O(1)的复杂度
by 梧桐灯 @ 2018-11-18 22:46:27


@[光随影走](/space/show?uid=31193) emmm~~好像明白了~~ 我去试试
by lizer @ 2018-11-18 22:49:13


@[光随影走](/space/show?uid=31193) A辣 蟹蟹神犇 ```cpp #include <iostream> using namespace std; struct carpet{ int a; int b; int g; int k; }a[100001]; int main() { int n,x,y; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b>>a[i].g>>a[i].k; cin>>x>>y; for(int i=n;i>=1;i--) if(x>=a[i].a&& x<=a[i].a+a[i].g&&y>=a[i].b&&y<=a[i].b+a[i].k){ cout<<i; return 0; } return 0; } ``` 代码也简洁了好多呢
by lizer @ 2018-11-18 22:54:48


|