造篱笆

柿子饼同学

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

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s;
}
int n;
int a[1000005];
int cnt[4005],ans[500005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        cnt[a[i]]++;
    }
    for(int i=2;i<=4000;i++)
    {
        int temp=0;
        for(int j=1;j<=i/2;j++)
        {
            if(j!=i-j) temp+=min(cnt[j],cnt[i-j]); // 这一行是什么意思
            else temp+=cnt[j]/2; // 还有这个
        }
        ans[temp]++;
    }
    for(int i=n/2;i>=1;i--)
    {
        if(ans[i]!=0)
        {
            printf("%d %d",i,ans[i]);
            return 0;   
        }       
    }
    return 0;
}

输入输出 :

Sample Input 1
4
1 2 3 4

Sample Input 2
5
1 10 100 1000 2000

Output 1
2 1

Output 2
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
帮我看看呗

首先先理解什么是数组 a、cnt 和 ans。

a 是木板长度
cnt[i] 是木板数量（依长度分配），i 是木板长度
ans[i] 是方案数量，i 是共几块木板

代码中你所问的 if(j!=i-j) temp+=min(cnt[j],cnt[i-j]);（第 34 行）的意思：
i 是两块木板长度之和
j 是其中一块木板的长度

当 j != i-j 这里表示两块木板不同长度时，则 temp+=min(cnt[j], cnt[i-j])
temp+=min(cnt[j], cnt[i-j]) 这行代码中，temp 是木板数量
而 cnt[j] 和 cnt[i - j] 分别是长度为 j 和长度为 i - j 的木板数量

例子一：
i = 7，j = 3，
长度为 3 的木板数量是 5 个
长度为 4 的木板数量是 2 个
那么
min(cnt[j], cnt[i-j])
= min(cnt[3], cnt[4])
= min(5, 2)
= 2
题解是最多造 2 块篱笆，这是其中的一种方案（各个木板长度分别是 4+3 和 4+3 共两块篱笆）

例子二：
i = 10，j = 5
长度为 5 的木板数量是 8 个
那么 j == i-j == 5（表示两块木板相同长度）则...
temp += cnt[j]/2
= temp += cnt[5]/2
= temp += 8/2
= 4
题解是最多造 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 就可以了
难道不会有多个解吗

第 37 行 ans[temp]++

傻眼貓咪

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

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