P10189 [USACO24FEB] Maximizing Productivity B (样例过了听取WA声一片)

Question

洛谷讨论Link

Code(5pts)

#include <iostream>
#include <cstdio>
#define int long long 
using namespace std;

int n, q, iC, v, s;
int c[200006], t[200006], R[1000006];

int Read () {
    int i;
    cin >> i;
    return i;
}

signed main () {
    n = Read(), q = Read();
    for (int i = 1; i <= n; i++)
        c[i] = Read();
    for (int i = 1; i <= n; i++)
        t[i] = Read();
    
    for (int i = 1; i <= n; i++) {
        iC = c[i] - t[i] - 1;
        if (iC > 0)
            R[iC] = R[iC] + 1;
    }
    
    for (int i = 1000000; i >= 1; i--)
        R[i] += R[i + 1];
        
    while (q--) {
        v = Read(), s = Read();
        if (R[s] == v)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

谢谢QaQ

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，您尝试解决的是 USACO 2024年2月的题目 "Maximizing Productivity B"。根据题目描述（虽然没有直接提供），该问题通常会涉及到奶牛挤奶的时间安排，以最大化连续不工作的天数。给定每个奶牛 c[i] 的挤奶周期和恢复期 t[i]，目标是判断对于任意询问 (v, s)，是否存在恰好 v 头奶牛可以安排它们的挤奶时间使得它们连续有 s 天不工作。

您的代码逻辑如下：

1. 读取输入数据：读取奶牛数量 n 和查询次数 q，接着读取每个奶牛的挤奶周期 c[i] 和恢复期 t[i]。

2. 统计连续空闲天数分布：

   • 计算每个奶牛能够贡献的连续空闲天数 iC = c[i] - t[i] - 1（这里假设挤奶后需要一天休息，所以实际连续空闲天数比周期少两天）。
   • 将统计结果存储到数组 R[] 中，其中 R[i] 表示有多少头奶牛能提供至少连续 i 天的空闲时间。

3. 前缀和计算：

   • 对数组 R[] 进行前缀和计算，使得 R[i] 变为“至少有连续 i 天空闲”的奶牛总数（包括那些能提供更多连续空闲天数的奶牛）。

4. 处理查询：

   • 遍历所有查询 (v, s)，判断是否存在恰好 v 头奶牛可以满足连续 s 天不工作的要求。
   • 如果存在，则输出 "YES"；否则，输出 "NO"。

根据您提供的代码片段，逻辑上看起来是正确的，但需要注意以下几点来确保程序运行无误：

• 确保输入的数据范围不会导致数组越界。
• 检查是否正确处理了边界情况，例如当 c[i] <= t[i] 时，奶牛无法贡献任何连续空闲天数。

由于样例已经通过，但提交到 OJ 后出现大量 WA (Wrong Answer)，那么可能存在的问题包括但不限于：

• 数据范围问题：检查是否考虑到了足够大的数据范围，比如 c 和 t 的最大值，以及数组大小是否合适。
• 查询条件的判断逻辑：确保在遍历查询时准确地统计了符合条件的奶牛数量。
• 输入格式或输出格式细节：确认程序对输入和输出格式的理解和处理完全符合题目的要求。

如果多次WA，建议重新审视题目描述，确保理解无误，并针对测试用例进行调试。此外，在此提供的代码中并未发现明显错误，若有更多关于WA的详细信息（如具体测试点、错误提示等），可以帮助进一步定位问题所在。