Supermarket

Time limit: 10 Seconds   Memory limit: 32768K  
Total Submit: 134   Accepted Submit: 70  

A supermarket has a set Prod of products on sale. It earns a profit px for each product x in Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell (subset of Prod) such that the selling of each product x in Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=sum of px (x in Sell). An optimal selling schedule is a schedule with a maximum profit.

在一个超市里，有一系列商品出售。从开始出售到截止期dx前，它可以获得利润px。每件商品精确地花费一个单位时间。一张销售计划表是一个销售商品的顺序子集，它包括了每个商品的利润px，和它的销售时间（次序），这个时间必须小于等于dx。销售计划的总利润是每个px的总和。最优解是使总利润最大化的计划表。注意：每个商品只有一件。

For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.

以下例说明。考虑{a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1)。可能的销售计划如表1。例如，{d,a}显示的是d在0时刻开始1时刻结束，a在1时刻开始2时刻结束。每一个商品在它的截止时间前销售。这种计划是最优解，答案是80.

Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.

A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.

For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.

The sample input in contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.

Sample Input

4 50 2 10 1 20 2 30 1

7 20 1 2 1 10 3 100 2 8 2
5 20 50 10

Sample Output

80
185

Problem Source: Southeastern Europe 2003

Submit   Back   Status

 #include <cstdio>
#include <string>
#include <cstdlib>

typedef struct
{
 int p, d;
} Prod;
Prod p[10001];

int n, d[10001], min[10001];

int cmp_p ( const void *a, const void *b )
{
 Prod *A = (Prod *)a;
 Prod *B = (Prod *)b;
 if ( A->d == B->d ) return ( A->p - B->p );
 return ( A->d - B->d );
}

int calc ()
{
 int i, k, j, pi, di, sum = 0, mini;
 memset ( d, 0, sizeof (d) );
 for ( i = 0; i < n; i ++ )
 {
  pi = p[i].p, di = p[i].d;
  mini = pi, j = -1;
  for ( k = di; k >= 1; k -- )
  {
   if ( d[k] < mini )
   {
    mini = d[k], j = k;
   }
  }
  if ( j != -1 ) d[j] = pi;
 }
 for ( i = 0; i <= 10000; i ++ )
 {
  sum += d[i];
 }
 return sum;
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 while ( scanf ( "%d", &n ) != EOF )
 {
  int i;
  for ( i = 0; i < n; i ++ )
   scanf ( "%d %d", &p[i].p, &p[i].d );
  qsort ( p, n, sizeof (Prod), cmp_p );
  //pp (); 
  printf ( "%d\n", calc () );
 }
 return 0;
}

评论