PROBLEM LINK:
Author: Aryan Agarwala
Tester: Felipe Mota
Editorialist: Rajarshi Basu
DIFFICULTY:
Cakewalk
PREREQUISITES:
Implementation
PROBLEM:
Chef has N items in his shop (numbered 1 through N) for each valid i, the price of the i^{th} item is P_i. Since Chef has very loyal customers, all N items are guaranteed to be sold regardless of their price.
However, the government introduced a price ceiling K, which means that for each item i such that P_i>K, its price should be reduced from P_i to K.
Chef’s revenue is the sum of prices of all the items he sells. Find the amount of revenue which Chef loses because of this price ceiling.
EXPLANATION:
Just simulate whatever is said!
Let’s say the loss in income for Chef is given by the variable loss.
For every element in the array P_i, the price at which it will be sold at is max(P_i, K). (think why?)
Thus, for every element i,
loss= loss + (P_i - max(P_i,K))
The complexity for this solution is O(N), as for every i, we only do a max operation, and a subtraction.
SOLUTIONS:
Setter's Code
#include <bits/stdc++.h>
#define int long long
#define INF 10000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
using namespace std;
signed main(){
int t, n, k, num, ans;
cin>>t;
while(t--){
cin>>n>>k;
ans = 0;
for(int i = 0;i<n;i++){
cin>>num;
ans+=max((int)0, num - k);
}
cout<<ans<<endl;
}
return 0;
}
Tester's Code
t = int(raw_input())
while t > 0:
n, k = map(int, raw_input().split())
print sum([max(x - k, 0) for x in map(int, raw_input().split())])
t -= 1
Please give me suggestions if anything is unclear so that I can improve. Thanks