不诚实的卖家题解

题目描述

伊戈尔发现有一家商店正在打折，所以决定在这家商店购买n件商品。商店的打折活动会持续一周，打折期间每件商品的价格是ai，等打折活动结束后，商品的价格变为bi。但是并非所有卖家都诚实，因此打折期间某些商品的价格可能会比折扣活动结束后的价格更贵。
伊戈尔决定现在至少购买k件商品，剩下的商品等活动结束后再购买。你的任务是帮伊戈尔计算一下用于购买n件商品的最低费用。

输入格式:
第一行包含两个正整数n和k（1≤n≤2e5，0≤k≤n），分别表示伊戈尔要购买的商品数量和他现在只少要买的商品数。
第二行包含n个整数 a1，a2，...，an（1≤ai≤1e4），分别表示折扣期间各个商品的价格。
第三行包含n个整数 b1，b2，...，bn（1≤bi≤1e4），分别表示折扣结束后商品的价格。

输出格式:
伊戈尔购买n件商品所需的最低金额。

解题思路

1.使a[i]=a[i]-b[i]表示折扣前后购买商品的差值（负表示省钱，正表示费钱）
2.非降序排列a[i]，累加满足a[i]<0的项，若不足k项，则继续累加
3.第2步的累加和加上b[i]的累加和为答案

完整代码

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
	int n, k, i, ans = 0, sum = 0;
	static int a[200020], b[200020];
	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (i = 0; i < n; i++) {
		scanf("%d", &b[i]);
		sum += b[i];
		a[i] -= b[i];
	}
	sort(a, a + n);
	for (i = 0; a[i] <= 0; i++) {
		ans += a[i];
	}
	for (; i < k; i++) {
		ans += a[i];
	}
	ans += sum;
	printf("%d", ans);
	return 0;
}