azatu

Хотел узнать в чем моя ошибка и правильная ли у меня идея. Вот код:

#include <iostream>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
#include <time.h>
#include <set>
#include <queue>
#include <unordered_set>
#include <fstream>
using namespace std;
#define ll long long

void fc (){
	ll n,m,k;
	cin>>n>>k;
	ll l=k+1,r=0,mx=0;
	ll a[n+5];
	for (int i=0; i<n; i++){
		cin>>a[i];
		mx=max(mx,a[i]);
	}r=mx;;
	ll res1,res2;
	for (int it=0; it<100; it++){
//		cout<<l<<" "<<r<<"\n";
		ll mid1=(2*l+r)/3,mid2=(l+2*r)/3;
		
		res1=0,res2=0;
		
		for (int i=0; i<n; i++){
			res1+=a[i]/mid1;	
			res2+=a[i]/mid2;
		}
		res1*=mid1-k;
		res2*=mid2-k;
		
		if (res1<res2){
			l=mid1;
		}else{
			r=mid2;
		}
		
	}
	ll ans=0;
//	cout<<max(res1,res2);
	for (int i=l; i<=r; i++){
		ll res=0;
		for (int j=0; j<n; j++){
			res+=a[j]/i;
		}res*=i-k;
		ans=max(ans,res);
	}
	
	ll res=0;
	for (int j=0; j<n; j++){
		res+=a[j]/(k+1);
	}
	ans=max(ans,res);
	res=0;
	for (int j=0; j<n; j++){
		res+=a[j]/(mx);
	}res*=mx-k;
	ans=max(ans,res);
	
	cout<<ans;
	
}


int main (){
	int T=1;
//	cin>>T;
	while (T--)  fc();
  
  
  
}```

MansurL

Привет, попробуй подумать в другом направлении

Подсказка (нажмите для более подробной информации)

Anton верхний кварк

@eudaimon how would you assess the code written by the student? The initial problem statement is this:

“You sell ice cream. A cost of production is k. Thus, if you sell ice cream at price x, your profit is x-k. There are n clients. For each client i we know the amount of money he’s willing to spend on ice cream, s_i. Choose the price of ice cream to maximize profits.”

1 ответ

sophia истинный кварк

To maximize profits, you must select a price that optimizes the balance between the number of ice creams sold and the profit per ice cream. The provided code attempts to solve the problem using a ternary search on the price; however, there are some considerations to address:

1. The ternary search assumes the function being optimized is unimodal (has only one maximum point) within the search interval. This may not hold true for discrete distributions of client money s_i. The profit function may not be smooth and unimodal due to the discrete nature of the clients’ money.

2. The choice to iterate 100 times is arbitrary and may not guarantee the optimal solution within the desired precision. It is important to define the termination condition for the search more precisely, possibly based on the difference between l and r.

3. The code calculates res1 and res2 by dividing each a[i] by mid1 and mid2 respectively, assuming each client will buy exactly a[i] / price ice creams. This might not reflect the actual problem’s constraints if each client can only buy one ice cream.

4. The code assumes that each client spends their entire budget, which might not be the case. Clients may choose not to buy ice cream if the price is higher than their budget.

5. The profit is calculated as (price - k) * number_of_ice_creams_sold. This needs to be correct according to the problem statement, but the algorithm must ensure that the number of ice creams sold is correctly computed.

6. The final check for maximum value at the end of the search (l <= i <= r) and the checks for k+1 and mx might not be necessary if the ternary search is correctly implemented.

Therefore, the student should verify the assumptions made by the ternary search and ensure it is the correct approach for this problem. If the profits function is not unimodal, a different optimization technique might be more appropriate. Additionally, the student should consider the discrete nature of the problem and ensure that the number of ice creams sold to each client is calculated correctly.

Anton верхний кварк

@eudaimon could you solve this problem with the interval approach? If so, do not reveal the solution, simply give some helpful (but not revealing) hint.

1 ответ

sophia истинный кварк

Consider the essence of the problem: each client will only buy ice cream if the price is less than or equal to the amount they are willing to spend. Therefore, for any given price, only the clients with a budget equal to or greater than this price will make a purchase.

Now, ponder on this: if you sort the clients based on the amount they are willing to spend and then iterate through these sorted values, you can determine how many clients will buy the ice cream at each of those price points. This way, you create intervals of possible prices.

Reflect on the following: for each potential price that corresponds to a client’s budget, calculate the profit you would make if you set the ice cream’s price at that value. Keep in mind the cost of production k. You seek the maximum profit, which is the maximum of these calculated profits.

The hint I shall bestow upon you is to consider the sorted budgets of the clients as the potential prices for the ice cream and to calculate the profit for each of these prices. The profit at each price is the number of clients who would buy at that price multiplied by the profit margin (price - k). The price that yields the highest profit is the solution to your quest.