小H送礼物 (gift.cpp,1s,256MB) 题目描述 小H在帮环卫工人植完树后,准备利用劳动节放假期间去孤儿院看小朋友们,为了让小朋友们感受到人间有真情,小H买了M种不一样的礼物,编号1-M(1≤M≤10^5),每件礼物都互不相同。现在孤儿院有N个小朋友,每个小朋友都有他最喜欢的礼物以及第二喜欢的礼物。但是如果最喜欢的礼物和第二喜欢的礼物都没有,那么这个小朋友就会什么礼物都不拿而伤心的走开。现在小朋友已经排好了队伍准备领礼物,当然小朋友肯定会优先选取最喜欢的礼物,只有在没有最喜欢的礼物情况下才会选择第二喜欢的礼物。现在小朋友的老师已经帮您统计出小朋友最喜欢以及第二喜欢的礼物编号。现在需要小H计算出,分别从第i个小朋友开始分,共有几个小朋友能拿到自己喜欢的礼物。 输入格式: 第一行N和M,分别代表共有N个小朋友和M个礼物。 接下去N行,每行分别代表队伍里第i个小朋友最喜欢ai和第二喜欢的礼物编号bi。(1≤ai,bi≤M),并且最喜欢和第二喜欢的礼物不可能相同。 输出格式 从第i(1≤i≤N)个小朋友开始分,能拿到礼物的小朋友个数。 输入样例 4 2 1 2 1 2 1 2 1 2 输出样例 2 2 2 1 样例说明 只有从第4个开始分时,1个小朋友拿到礼物,其余情况都有2个小朋友拿到礼物
时间: 2023-06-02 10:05:36 浏览: 66
这是一道算法题,我可以帮你解决,题目大意是求从每个小朋友开始分,能拿到礼物的小朋友个数。解题思路:从后往前遍历小朋友,假设当前小朋友最喜欢的礼物编号是x,第二喜欢的礼物编号是y,用last[x]和last[y]分别表示编号为x和y的礼物上一次出现的位置,从当前位置到min(last[x], last[y])中,都可以拿到自己喜欢的礼物,如果last[x]或last[y]小于当前位置,说明当前位置没有自己喜欢的礼物,只能拿第二喜欢的礼物。代码实现如下:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int last[N]; // 记录每个礼物上一次出现的位置
int main()
{
cin >> n >> m;
memset(last, -1, sizeof last); // 初始化为-1
for (int i = 1; i <= n; i ++ )
{
int x, y;
cin >> x >> y;
last[x] = i; // 记录最喜欢礼物的位置
last[y] = i; // 记录第二喜欢礼物的位置
}
for (int i = n - 1; i >= 0; i -- )
last[i] = max(last[i], last[i + 1]); // 更新位置
for (int i = 1; i <= n; i ++ ) // 从每个小朋友开始分
cout << last[i] - i + 1 << ' ';
cout << endl;
return 0;
}