首页 > ACM题库 > HDU-杭电 > hdu 3738 The Sweat Shop[解题报告]C++
2015
02-22

hdu 3738 The Sweat Shop[解题报告]C++

The Sweat Shop

问题描述 :

Many people spend thier lives in sweat shop in China. The boss of one of the famous sweat shop, GXX, is considering about the employment plan of her company.
He already knows that in the next N days, how many worker are needed for this day’s work, a[i]. In additional, he will spend x yuan on recruit a worker, y yuan on fire a worker. If a worker spend a day on work in his company, GXX must pay z yuan for the wages per day.
GXX has no work before the first day and he decide to fire all the workers after these N days. Now comes to the question, how much he will pay on the employment plan in minimum.

输入:

The first line contains only one integer T, denoting the number of test cases.
For each test cases, the first line contains only one integer N, denoting the number of days. (1 <= N <= 100000)
The next line contains three integers, x, y and z, denoting the amount of spend on recruit, fire a worker, and the daily salary of a worker. (1 <= x,y,z <= 100000)
The third line contains N integers, a[i], denoting the minimum number of workers needed for the i-th day. (1 <= a[i] <= 100000)

输出:

The first line contains only one integer T, denoting the number of test cases.
For each test cases, the first line contains only one integer N, denoting the number of days. (1 <= N <= 100000)
The next line contains three integers, x, y and z, denoting the amount of spend on recruit, fire a worker, and the daily salary of a worker. (1 <= x,y,z <= 100000)
The third line contains N integers, a[i], denoting the minimum number of workers needed for the i-th day. (1 <= a[i] <= 100000)

样例输入:

1
3
10 10 1
2 1 2

样例输出:

46

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define N 100010
int n;
__int64  a[N], x, y, z;
int q[N], ed;
__int64 min(__int64 a,__int64 b )
{
 return a<b?a:b;   
}
void solve() {
    __int64 res = a[0] * x + a[n - 1] * y;
    for (int i = 0; i < n; ++i) {
        res += a[i] * z;
        if(i) {
            if (a[i - 1] > a[i])
                res += (a[i - 1] - a[i]) * y;
            else
                res += (a[i] - a[i - 1]) * x;
        }
    }
    ed = 0;
    q[ed++] = 0;
    for (int i = 1; i < n; ++i) {
        if (a[q[ed - 1]] >= a[i]) q[ed++] = i;
        else {
            while (ed > 1 && a[q[ed - 1]] < a[i]) {
                --ed;
               /* t是解雇工人的数目 ,
                  tmp---是留着这个工人省钱还是解雇这个工人省的钱 ?? 
               */
                __int64 tmp, t = min(a[i], a[q[ed - 1]]) - a[q[ed]];

                if ((tmp = (x + y - (i - q[ed - 1] - 1) * z) * t) > 0) {

                    res -= tmp;
                     //printf("\n........\nq[ed]=%d l=%d r=%d tmp=%d\n",q[ed],q[ed - 1],i,tmp);
                }
            }
            if (a[q[ed - 1]] <= a[i]) --ed;
            q[ed++] = i;

        }
    }
    printf("%I64d\n", res);
}
int main() {
    freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
    int cas;
    scanf("%d", &cas);
    while (cas--) {
    scanf("%d", &n);
    scanf("%I64d%I64d%I64d", &x, &y, &z);
    for (int i = 0; i < n; ++i) {
        scanf("%I64d", &a[i]);
    }
        solve();
    }
    return 0;
}

  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。