【NOIP2012模拟10.6】购买

Description

小N 最近迷上了购物每天都让小A 和小T 陪她逛街拿东西。最近商店出了这样的一个
活动:买东西送积分，就是买一件物品，送当前物品的积分ci*当前的倍率，初始倍率是1；
当倍率是i 的时候，如果你买的物品等于ti 个，那么倍率将加1.最多积分的人可以得到超限量版的圆神手办。小N 十分喜欢这个手办但是她又有自己的购物计划，于是她想在这个计划下尽量提高自己的积分。她有n 种东西要买，其中第i 种物品她要买ki 个，每个可以得到ci 的积分。请告诉她积分最多能得到多少吧。

Input

第一行有一个整数n表示要买的种类。
接下来n行每行2个整数ki,ci表示数量和积分
接下来一行有一个正整数t表示奖励的倍数
接下来一行有t个递增的整数ti表示买了ti个物品之后以后买的物品得到的积分倍率将是(i+1)

Output

一个整数，表示小N能得到的最多积分

题解

从小到大排序，贪心策略。

代码

var
  ans,sum:int64;
  n,m:longint;
  ki,ci,t:array [1..101] of int64;
procedure init;
var
  i,j:longint;
begin
  readln(n);
  sum:=0;
  for i:=1 to n do
    begin
      readln(ki[i],ci[i]);
      sum:=sum+ki[i];
    end;
  readln(m);
  for i:=1 to m do
    read(t[i]);
  for i:=2 to m do
    for j:=1 to i-1 do
      t[i]:=t[i]-t[j];
end;

procedure qsort(l,r:longint);
var
  i,j:longint;
  mid,tt:int64;
begin
  if l>=r then exit;
  i:=l; j:=r;
  mid:=ci[(l+r) div 2];
  repeat
    while ci[i]<mid do inc(i);
    while ci[j]>mid do dec(j);
    if i<=j then
      begin
        tt:=ci[i]; ci[i]:=ci[j]; ci[j]:=tt;
        tt:=ki[i]; ki[i]:=ki[j]; ki[j]:=tt;
        inc(i); dec(j);
      end;
  until i>j;
  qsort(i,r);
  qsort(l,j);
end;

procedure main;
var
  p,q,ti,i:longint;
  k:int64;
begin
  k:=0; ans:=0;
  p:=1; q:=1; ti:=1;
  while k<sum do
    begin
      if t[p]<ki[q] then
        begin
          ans:=ans+t[p]*ci[q]*ti;
          ki[q]:=ki[q]-t[p];
          inc(ti);
          k:=k+t[p];
          inc(p);
        end else
        begin
          ans:=ans+ki[q]*ci[q]*ti;
          t[p]:=t[p]-ki[q];
          k:=k+ki[q];
          inc(q);
        end;
        if p>m then
          begin
            for i:=q to n do
              ans:=ans+ci[i]*ki[i]*ti;
            k:=sum;
          end;
    end;
  write(ans);
end;


begin
  init;
  qsort(1,n);
  main;
end.