山东省第八届ACM省赛 J 题 company（两种思路）解答

你的名字 2022-06-10 10:56 224阅读 0赞

# company #

# Time Limit: 1000MS Memory Limit: 65536KB #

## Problem Description ##

There are *n* kinds of goods in the company, with each of them has a inventory of ![3902-1.png][] and direct unit benefit ![3902-2.png][]. Now you find due to price changes, for any goods sold on day *i*, if its direct benefit is *val*, the total benefit would be  *i*⋅*val*.  
Beginning from the first day, you can and must sell only one good per day until you can't or don't want to do so. If you are allowed to leave some goods unsold, what's the max total benefit you can get in the end?

## Input ##

The first line contains an integers *n*(1≤*n*≤1000).  
The second line contains *n* integers *val*1,*val*2,..,*valn*(−100≤![3902-2.png][].≤100).  
The third line contains *n* integers *cnt*1,*cnt*2,..,*cntn*(1≤![3902-1.png][]≤100).

## Output ##

Output an integer in a single line, indicating the max total benefit.

## Example Input ##

4
    -1 -100 5 6
    1 1 1 2

## Example Output ##

##     ##

## Hint ##

sell goods whose price with order as -1, 5, 6, 6, the total benefit would be -1\*1 + 5\*2 + 6\*3 + 6\*4 = 51.

## 题意： ##

商店中有 N 种商品，第 i 种商品的库存有 cnt(i) 件，单价是 val(i) 。现在由于价格变动，你需要开始卖 东西。规则是，每天必须卖一件商品（除非卖光了或者你以后不想再卖了），（注意：每天卖出的是一件商品不是一种商品，没一件商品你都可以决定卖与不卖），这件商品的利润是：

i (第 i 天) \* 这件商品的val 。可以由测试案例核实。求 最大利润。

## 思路 1 ： ##

把每件商品，单个摆开，排成一排，然后根据商品价值对这一排 进行升序排序，找到第一个不是负数的数，记录位置，然后把这个位置之后的（包括它自己）按顺序全卖，记录此时的利润 sum, 然后把这个位置往前移一位，再进行，记录得到的最大的价值 max;

## AC代码： g++ 780ms ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define maxn 100010
    #define INF 0x3f3f3f3f
    using namespace std;
    int d[maxn];
    int n,v[1010],c[1010];
    long long sum,MAX;
    int main()
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&v[i]);
        for(int i=0; i<n; i++)
            scanf("%d",&c[i]);
        int ii=1;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<c[i]; j++)
            {
                d[ii++]=v[i];
            }
        }
        sort(d+1,d+ii);
        d[0]=-1;  //这个地方是为了避免全是正数或者全是负数的情况；
        d[ii]=1;
        int xx=0;
        for(int i=1; i<ii; i++) //找的第一个不是负数的数；
        {
            if(d[i]>=0&&d[i-1]<0)
            {
                xx=i;
                break;
            }
        }
        MAX=-INF;
        for(int i=0; i<xx; i++) //挨个的往前取，并把最大的保存；
        {
            int day=1;
            sum=0;
            for(int j=xx-i; j<ii; j++)
            {
                sum+=day*d[j];
                day++;
            }
            if(MAX<sum) MAX=sum;
        }
        cout<<MAX<<endl;
        return 0;
    }
    //http://blog.csdn.net/qq_36949416/article/details/71598163）

## 思路 2： ##

从后往前处理，因为 价值最大的，总是在最后一天卖掉，这样利润才会最大。这样，每次 累加 的时候，总会把价值最大的考虑在内

假设不考虑 天数 i 的影响，光单价就不足以营利 的时候，显然这时候就应该停止了。

## AC代码： g++ 4ms (思路很好)    ##

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    typedef long long ll;
    int n;
    ll a[110000];
    ll sum[110000];
    bool cmp(int a,int b)
    {
    	return a>b;
    }
    int main()
    {
    	ll t[1100];
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(int i=0;i<n;i++)
    			scanf("%lld",&t[i]);
    		int k=0;
    		for(int i=0;i<n;i++) {
    			int count;
    			scanf("%d",&count);
    			while(count--) {
    				a[k++]=t[i];
    			}
    		}
    		sort(a,a+k,cmp);    //降序排列
    		sum[0] = a[0];
    		for(int i=0;i<k;i++)
                            sum[i]=sum[i-1]+a[i];
    		ll ans=0;
                   for(int i=0;i<k;i++) {
    			if(sum[i] >= 0)
    				ans  += sum[i];
    			else       
    				break;
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }
    //http://blog.csdn.net/winter2121/article/details/71698099

[3902-1.png]: http://acm.sdut.edu.cn/image/3902-1.png
[3902-2.png]: http://acm.sdut.edu.cn/image/3902-2.png