造篱笆

柿子饼同学

题目在下, 不知道题解是什么意思 , 为什么这么写 , 求助

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. inline int read()
   
4. {
   
5.     int s=0;
   
6.     char c=getchar();
   
7.     while(c<'0'||c>'9')
   
8.     {
   
9.         c=getchar();
   
10.     }
    
11.     while(c>='0'&&c<='9')
    
12.     {
    
13.         s=(s<<3)+(s<<1)+(c^48);
    
14.         c=getchar();
    
15.     }
    
16.     return s;
    
17. }
    
18. int n;
    
19. int a[1000005];
    
20. int cnt[4005],ans[500005];
    
21. int main()
    
22. {
    
23.     n=read();
    
24.     for(int i=1;i<=n;i++)
    
25.     {
    
26.         a[i]=read();
    
27.         cnt[a[i]]++;
    
28.     }
    
29.     for(int i=2;i<=4000;i++)
    
30.     {
    
31.         int temp=0;
    
32.         for(int j=1;j<=i/2;j++)
    
33.         {
    
34.             if(j!=i-j) temp+=min(cnt[j],cnt[i-j]); // 这一行是什么意思
    
35.             else temp+=cnt[j]/2; // 还有这个
    
36.         }
    
37.         ans[temp]++;
    
38.     }
    
39.     for(int i=n/2;i>=1;i--)
    
40.     {
    
41.         if(ans[i]!=0)
    
42.         {
    
43.             printf("%d %d",i,ans[i]);
    
44.             return 0;   
    
45.         }      
    
46.     }
    
47.     return 0;
    
48. }

复制代码

输入输出 :

1. Sample Input 1
   
2. 4
   
3. 1 2 3 4
   
4. 
   
5. Sample Input 2
   
6. 5
   
7. 1 10 100 1000 2000

复制代码

1. Output 1
   
2. 2 1
   
3. 
   
4. Output 2
   
5. 1 10

复制代码

回答有渔币 , 谢谢大家了 , 过两个月考试

柿子饼同学

它就是先枚举篱笆的长度 , 再枚举一个木板的长度
但是下面是什么意思不知道

傻眼貓咪

为什么不用 std::cin ？ 为什么另外写 inline int read() ？很奇怪...

柿子饼同学

傻眼貓咪 发表于 2022-7-12 09:09
为什么不用 std::cin ？ 为什么另外写 inline int read() ？很奇怪...

哦 , 他们追求极致的速度

傻眼貓咪

柿子饼同学 发表于 2022-7-12 09:55
哦 , 他们追求极致的速度

明白了

柿子饼同学

傻眼貓咪 发表于 2022-7-12 10:05
明白了

柿子饼同学

傻眼貓咪 发表于 2022-7-12 10:05
明白了

帮我看看呗

傻眼貓咪

柿子饼同学 发表于 2022-7-12 19:48
帮我看看呗

1. 首先先理解什么是数组 a、cnt 和 ans。
   
2. 
   
3. a 是木板长度
   
4. cnt[i] 是木板数量（依长度分配），i 是木板长度
   
5. ans[i] 是方案数量，i 是共几块木板
   
6. 
   
7. 代码中你所问的 if(j!=i-j) temp+=min(cnt[j],cnt[i-j]);（第 34 行）的意思：
   
8. i 是两块木板长度之和
   
9. j 是其中一块木板的长度
   
10. 
    
11. 当 j != i-j 这里表示两块木板不同长度时，则 temp+=min(cnt[j], cnt[i-j])
    
12. temp+=min(cnt[j], cnt[i-j]) 这行代码中，temp 是木板数量
    
13. 而 cnt[j] 和 cnt[i - j] 分别是长度为 j 和长度为 i - j 的木板数量
    
14. 
    
15. 例子一：
    
16. i = 7，j = 3，
    
17. 长度为 3 的木板数量是 5 个
    
18. 长度为 4 的木板数量是 2 个
    
19. 那么
    
20. min(cnt[j], cnt[i-j])
    
21. = min(cnt[3], cnt[4])
    
22. = min(5, 2)
    
23. = 2
    
24. 题解是最多造 2 块篱笆，这是其中的一种方案（各个木板长度分别是 4+3 和 4+3 共两块篱笆）
    
25. 
    
26. 例子二：
    
27. i = 10，j = 5
    
28. 长度为 5 的木板数量是 8 个
    
29. 那么 j == i-j == 5（表示两块木板相同长度）则...
    
30. temp += cnt[j]/2
    
31. = temp += cnt[5]/2
    
32. = temp += 8/2
    
33. = 4
    
34. 题解是最多造 4 块篱笆，这是其中的一种方案（各个木板长度分别是 5+5 和 5+5 和 5+5 和 5+5 共四块篱笆）

复制代码

柿子饼同学

傻眼貓咪 发表于 2022-7-12 20:26

那 39 - 46 行为什么只需要 ans[i] != 0 就可以了
难道不会有多个解吗

傻眼貓咪

柿子饼同学 发表于 2022-7-13 09:11
那 39 - 46 行为什么只需要 ans != 0 就可以了
难道不会有多个解吗

1. 第 37 行 ans[temp]++

复制代码

傻眼貓咪

柿子饼同学 发表于 2022-7-13 09:11
那 39 - 46 行为什么只需要 ans != 0 就可以了
难道不会有多个解吗

1. 你注意看我的解说里的第 5 行，ans[i] 是方案数量，i 是共几块木板

复制代码