← 返回题目列表

AtCoder · APG4b_cf

EX17. 第2.02节

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_cf

返回说明页面

問題文

在水果店,苹果和菠萝是分开出售的。N单独出售。i每个苹果和菠萝都是A_i円、P_i是日元。

当尝试选择并购买一个苹果和一个菠萝时,总价正好是S求出购买方式的数量,使其变成日元。

但是,同类型同价格的产品也存在差异化。例如,如果有多个价格相同的苹果,则每次购买都算作一次单独购买。菠萝也是如此。另外,我们不考虑苹果和菠萝的购买顺序。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  // ここにプログラムを追記
}

制約

  • 0≦N≦100
  • 0≦S≦1000
  • 1≦A_i, P_i≦500 (1 ≦ i ≦ N)
  • A_i, P_i (1 ≦ i ≦ N)是一个整数

入力

输入是从标准输入按以下格式给出的:

N S
A_1 A_2 \cdots A_N
P_1 P_2 \cdots P_N

出力

当尝试购买一个苹果和一个菠萝时,总价正好是S像一个圆圈 请打印出有多少种购买方式。

输出末尾需要换行符。


Judge还测试了除下面输入示例之外的情况。注意。

入力例1

3 400
100 100 130
270 300 250

出力例1

3

总共400日元共有三种购买方式:
如果您购买第一个苹果和第二个菠萝,则成本将为 100 日元 + 300 日元 = 400 日元。
如果你买第二个苹果和第二个菠萝,成本将是100日元+300日元=400日元。
如果购买第三个苹果和第一个菠萝,价格将为130日元+270日元=400日元。
请注意,虽然第一个苹果和第二个苹果都是 100 日元,但它们算作单独购买。

入力例2

10 600
70 110 90 120 90 20 260 150 220 150
170 100 250 350 60 280 450 460 20 220

出力例2

2

入力例3

3 200
100 100 100
100 100 100

出力例3

9

入力例4

1 0
100
200

出力例4

0

不能以总计 0 日元购买。


提示

  1. 不循环写入
  2. 查找模式
  3. 用循环重写 我会根据

编写时的流程并有提示。

先尝试自己思考一下,如果卡住了,就看一下。

技巧 1(无循环写入)

点击查看提示

总计为S我们正在寻找可以兑换日元的购买方式的数量。 如果您可以使用 if 语句检查所有组合,您应该能够找到答案。

一般N很难想象,因此在尝试时,最好假设 N 值较小。 让我们写出 N = 3的所有情况。 (请注意,我们使用基于 0 的值作为下标。)

  int ans = 0;

  if (A.at(0) + P.at(0) == S) {
    ans++;
  }
  if (A.at(0) + P.at(1) == S) {
    ans++;
  }
  if (A.at(0) + P.at(2) == S) {
    ans++;
  }

  if (A.at(1) + P.at(0) == S) {
    ans++;
  }
  if (A.at(1) + P.at(1) == S) {
    ans++;
  }
  if (A.at(1) + P.at(2) == S) {
    ans++;
  }

  if (A.at(2) + P.at(0) == S) {
    ans++;
  }
  if (A.at(2) + P.at(1) == S) {
    ans++;
  }
  if (A.at(2) + P.at(2) == S) {
    ans++;
  }

似乎可以通过关注下标的变化来创建模式。

提示 2(查找模式) 介绍

点击查看提示 変数i, j通过介绍i第一个苹果, 考虑购买第j个菠萝的情况。 条件表达式如下所示:

if (A.at(i) + P.at(j) == S) {
  ans++;
}

剩下的是 如果您可以详尽地运行i, j并执行上述语句,那就太好了。

提示3(循环重写) 购买第

点击查看提示

変数i, j通过介绍i第一个苹果, 考虑购买第j个菠萝的决策语句如下。

if (A.at(i) + P.at(j) == S) {
  ans++;
}

i, j分别从0开始 取值最大为N - 1。
变量(此处 如果要枚举i, j) 的组合,请使用多个循环。
在这种情况下,变量是i, j,所以它变成了如下的双循环。

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      // i, jを使う
    }
  }


测试输入/输出

只有当你写的程序没有变成AC并且你找不到原因时,请看这个。

单击查看测试输入/输出

测试输入 1
10 520
430 310 230 390 130 220 70 370 400 160
390 120 450 30 250 140 200 300 270 30
测试输出 1
4

测试输入 2
100 500
247 365 116 339 302 274 383 230 444 136 12 100 92 498 16 190 252 438 404 493 46 105 197 254 180 455 233 280 289 286 301 205 200 477 273 481 494 287 202 211 327 359 341 4 51 336 101 416 142 35 401 457 61 179 33 362 180 176 60 247 499 44 279 372 424 439 224 99 379 322 110 159 383 143 164 435 6 461 61 391 38 225 163 273 222 156 33 300 42 228 164 22 244 66 28 208 243 36 417 93
62 231 388 7 434 37 474 357 262 182 36 298 426 331 252 129 113 156 111 441 375 210 492 499 302 287 493 170 262 233 475 406 72 401 468 156 220 1 410 12 223 150 240 159 345 239 455 404 419 19 46 174 499 218 423 145 196 307 401 260 470 424 171 284 437 44 500 316 156 192 422 391 365 485 145 22 410 124 110 182 28 143 203 289 95 85 415 401 191 268 262 341 391 130 364 274 379 443 53 389
测试输出 2
15

测试输入 3
100 1000
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500
测试输出 3
10000


解答例

观看前请务必亲自尝试一下问题。

点击查看示例答案

解答例1

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  int ans = 0;  // 買い方が何通りあるか

  // 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (A.at(i) + P.at(j) == S) {
        ans++;
      }
    }
  }

  cout << ans << endl;
}

示例答案 2(使用语句范围的解决方案)

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, S;
  cin >> N >> S;
  vector<int> A(N), P(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> P.at(i);
  }

  // リンゴ・パイナップルをそれぞれ1つずつ購入するとき合計S円になるような買い方が何通りあるか
  int ans = 0;  // 買い方が何通りあるか

  // 実際に全ての買い方を試してみて、合計がS円ならカウントアップ
  for (int x : A) {
    for (int y : P) {
      if (x + y == S) {
        ans++;
      }
    }
  }

  cout << ans << endl;
}