首页 > 编程语言 > 详细

【codevs2476】购买贺年卡 排序+贪心

时间:2015-09-13 22:49:40      阅读:298      评论:0      收藏:0      [点我收藏+]

题目描述挺简单的,也很容易分析。可以作为练习快排和贪心使用

var
        t,f:array[0..1010] of longint;
        i,j,m,n,k,l:longint;

        procedure qsort(l,r:longint);
        var i,j,k,p:longint;
        begin
                i:=l;
                j:=r;
                k:=t[(i+j)>>1];
                repeat
                while t[i]<k do inc(i);
                while t[j]>k do dec(j);

                if i<=j then
                begin
                        p:=t[i];
                        t[i]:=t[j];
                        t[j]:=p;
                        p:=f[i];
                        f[i]:=f[j];
                        f[j]:=p;
                        inc(i);
                        dec(j);
                end;
                until i>j;
                if i<r then qsort(i,r);
                if j>l then qsort(l,j);
        end;

        begin
                readln(m,n);
                for i:=1 to n do
                read(t[i],f[i]);

                qsort(1,n);
                j:=1;      n:=m;
                while n<>0 do
                begin
                        if n>f[j] then
                        begin
                                inc(l,f[j]*t[j]);
                                inc(j);
                                dec(n,f[j-1]);
                        end else
                        begin
                                inc(l,n*t[j]);
                                n:=0;
                        end;
                end;
                writeln(l);
        end.

 

【codevs2476】购买贺年卡 排序+贪心

原文:http://www.cnblogs.com/victorslave/p/4805630.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!