洛谷 SP3591 题解

洛谷题目传送门 | SP 原题传送门

~~本题双倍经验，同主题库P2926~~

思路

~~又是一道~~桶的题。

首先暴力，对于 $N=100000$ ，复杂度 $O(n^2)$ ，显然超时。

考虑优化。

看题面，不难想到用桶记录每个数字的出现次数，只需要遍历数组找到比 $a_i$ 小的数即可。

但是这样仍然超时，继续优化。发现遍历数组时没必要全遍历一边，只需要遍历到 $\sqrt{n}$ 即可。

注意以下几点：

对于完全平方数， $\sqrt{n}$ 会计算两遍，此时答案数减一；
奶牛会拍到自己的头，答案数还需要减一。

~~然后就可以看见一篇绿色了。~~

代码

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=1e5+10;
int n,ans=0;
int a[N],t[1000010];
int main()
{
n=read();
for...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Makerlife 的小站
Makerlife 的小站
马上订阅 Makerlife 的小站 RSS 更新: https://blog.makerlife.top/atom.xml
洛谷 SP3591 题解
2022年7月9日 18:57
洛谷题目传送门 | SP 原题传送门
本题双倍经验，同主题库P2926
思路
又是一道桶的题。
首先暴力，对于  $N=100000$ ，复杂度  $O(n^2)$ ，显然超时。
考虑优化。
看题面，不难想到用桶记录每个数字的出现次数，只需要遍历数组找到比  $a_i$  小的数即可。
但是这样仍然超时，继续优化。发现遍历数组时没必要全遍历一边，只需要遍历到  $\sqrt{n}$  即可。
注意以下几点：
对于完全平方数， $\sqrt{n}$  会计算两遍，此时答案数减一；
奶牛会拍到自己的头，答案数还需要减一。
然后就可以看见一篇绿色了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=1e5+10;
int n,ans=0;
int a[N],t[1000010];
int main()
{
n=read();
for...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Makerlife 的小站
Makerlife 的小站
马上订阅 Makerlife 的小站 RSS 更新: https://blog.makerlife.top/atom.xml
洛谷 SP3591 题解
2022年7月9日 18:57
洛谷题目传送门 | SP 原题传送门
本题双倍经验，同主题库P2926
思路
又是一道桶的题。
首先暴力，对于  $N=100000$ ，复杂度  $O(n^2)$ ，显然超时。
考虑优化。
看题面，不难想到用桶记录每个数字的出现次数，只需要遍历数组找到比  $a_i$  小的数即可。
但是这样仍然超时，继续优化。发现遍历数组时没必要全遍历一边，只需要遍历到  $\sqrt{n}$  即可。
注意以下几点：
对于完全平方数， $\sqrt{n}$  会计算两遍，此时答案数减一；
奶牛会拍到自己的头，答案数还需要减一。
然后就可以看见一篇绿色了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int N=1e5+10;
int n,ans=0;
int a[N],t[1000010];
int main()
{
n=read();
for...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章