Accepted

状态 耗时 内存占用

#1 Accepted 3ms 380.0 KiB
#2 Accepted 3ms 360.0 KiB
#3 Accepted 3ms 380.0 KiB
#4 Accepted 3ms 348.0 KiB
#5 Accepted 3ms 364.0 KiB

代码简洁明了

#include<cstdio>
#include<algorithm>
using namespace std;
struct rule
{
int t,m;
}a[505];
bool cmp(rule x,rule y)
{
return x.m>y.m;
}
bool b[505];
int main()
{
int n,i,s=0,sx=0,o;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i].t);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].m);
s+=a[i].m;
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)
{
if(b[a[i].t])
{
o=1;
while(o<a[i].t)
{
if(!b[a[i].t-o])
{
b[a[i].t-o]=1;
sx+=a[i].m;
break;
}
o++;
}
}
if(!b[a[i].t])
{
b[a[i].t]=1;
sx+=a[i].m;
}
}
printf("%d\n",s-sx);
return 0;
}

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    vector<ll> d,w;
    
    void qs(ll l,ll r)
    {
        ll i=l,j=r;
        for (ll mid=d[(l+r)>>1];i<j;)
        {
            while (d[i]>mid)
                i++;
            while (d[j]<mid)
                j--;
            if (i<=j)
            {
                swap(d[i],d[j]),swap(w[i],w[j]);
                i++,j--;
            }
        }
        if (l<j)
            qs(l,j);
        if (i<r)
            qs(i,r);
    }
    
    struct heap
    {
        vector<ll> h;
        
        int cmp(ll x,ll y)
        {
            return w[h[x]]>w[h[y]];
        }
        
        void clear()
        {
            h.resize(1,-1);
        }
        
        void add(ll x)
        {
            h.push_back(x);
            for (ll i=h.size()-1;i>1&&cmp(i,i>>1);i>>=1)
                swap(h[i>>1],h[i]);
        }
        
        void pop()
        {
            h[1]=h[h.size()-1];
            h.pop_back();
            for (ll i=1,j;(i<<1)<h.size();i=j)
            {
                j=h.size();
                if (cmp(i<<1,i))
                    j=i<<1;
                if (((i<<1)|1)<h.size())
                {
                    if (cmp((i<<1)|1,i)&&cmp((i<<1)|1,i<<1))
                        j=(i<<1)|1;
                }
                if (j<h.size())
                    swap(h[i],h[j]);
            }
        }
        
        ll size()
        {
            return h.size()-1;
        }
        
        ll top()
        {
            return h[1];
        }
    };
    
    ll n,ans;
    heap h;
    
    void main()
    {
        while (~scanf("%lld",&n))
        {
            d.resize(n),w.resize(n);
            for (ll i=0;i<n;i++)
                scanf("%lld",&d[i]);
            for (ll i=0;i<n;i++)
                scanf("%lld",&w[i]);
            qs(0,n-1);
            h.clear();
            for (ll t=n,i=0,j;t>=1;t--)
            {
                for (j=i;j<n;j++)
                    if (d[j]<t)
                        break;
                for (;i<j;i++)
                    h.add(i);
                if (h.size()>0)
                    h.pop();
            }
            for (ans=0;h.size()>0;h.pop())
                ans+=w[h.top()];
            printf("%lld\n",ans);
        }
    }
}

int main()
{
    dts::main();
}

一个\(O(n \log n)\)的做法：按照截止时间从大到小处理，用堆维护所有能做的任务，每秒把误时惩罚最大的任务做掉就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("1604.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
pair<int,int> a[501];
priority_queue<int> q;
int main(){
    init();
    int n=readint();
    for(int i=1;i<=n;i++)
        a[i].first=readint();
    for(int i=1;i<=n;i++)
        a[i].second=readint();
    sort(a+1,a+n+1);
    for(int i=n;i;i--){
        q.push(a[i].second);
        int cnt=a[i].first-a[i-1].first;
        while((cnt--) && !q.empty())
            q.pop();
    }
    int ans=0;
    while(!q.empty()){
        ans+=q.top();
        q.pop();
    }
    printf("%d",ans);
}

#include <stdio.h>
#include <stdlib.h>
typedef struct{
    int time;
    int weight;
}obj,*object;

object objs;
int num = 0;//任务数
int totle = 0;
int order[500];//任务序列

//冒泡排序
void bubble(){
    obj tmp;
    for(int i=0;i<num-1;i++){
        for(int j=0;j<num-i-1;j++)
            if(objs[j].weight>objs[j+1].weight){
                tmp = objs[j];
                objs[j] = objs[j+1];
                objs[j+1] = tmp;
            }
    }
}

void range(){
    for(int i=num-1;i>=0;i--){
        if(order[objs[i].time]==0){
            order[objs[i].time] = 1;
        }else{
            int j = objs[i].time;
            bool change = false;
            for(;j>=1;j--)
                if(order[j]==0){
                    change = true;
                    order[j] = 1;
                    break;
                }
            if(!change)
                totle+=objs[i].weight;
        }
    }
}

int main()
{
    scanf("%d",&num);
    //初始化结构体对象
    objs = (object)malloc(num*sizeof(obj));
    for(int i=0;i<num;i++)
        scanf("%d",&objs[i].time);
    for(int i=0;i<num;i++)
        scanf("%d",&objs[i].weight);
    bubble();
    range();
    printf("%d",totle);
    return 0;
}

远看是动规，近看是贪心，仔细看发现是
纯净水！
var
a,b:array[1..500]of integer;
n,i,j,t,s:longint;
f:array[1..500]of boolean;
e:boolean;
begin
readln(n);
for i:=1 to n do read(a[i]);readln;
for i:=1 to n do read(b[i]);readln;
for i:=1 to n-1 do
for j:=n downto i+1 do
if b[j]>b[j-1] then begin
t:=b[j];b[j]:=b[j-1];b[j-1]:=t;
t:=a[j];a[j]:=a[j-1];a[j-1]:=t;
end;
for i:=1 to n do f[i]:=false;
for i:=1 to n do begin
e:=false;
for j:=a[i] downto 1 do if f[j]=false then begin
f[j]:=true;e:=true;break;
end;
if e=false then inc(s,b[i]);
end;
writeln(s);
end.

算法掌握后其实代码挺好写的，就是c语言没有自带的pair，qsort还不太好用，代码一写就长了。。。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct workRecord
{
int f;
int time;
};
typedef struct workRecord *Work;

int main(void)
{
int n;

scanf("%d", &n);
int fs[n+1], ts[n+1];
int i, j;
for (i = 1; i <= n; i++)
scanf("%d", &ts[i]);
for (i = 1; i <= n; i++)
scanf("%d", &fs[i]);

Work *W = (Work *) malloc(sizeof(Work) * (n+1));
for (i = 1; i <= n; i++)
{

W[i] = (Work) malloc(sizeof(struct workRecord));
W[i]->f = fs[i];
W[i]->time = ts[i];
}

Work temp;
for (i = 1; i <= n; i++)
{

temp = W[i];
for (j = i; j-1 >= 1 && W[j-1]->f < temp->f; j--)
W[j] = W[j-1];
W[j] = temp;
}

bool T[n+1];
for (i = 1; i <= n; i++)
T[i] = false;

int ans = 0;
for (i = 1; i <= n; i++)
{

int t = W[i]->time;
while (T[t] && t >= 1)
t--;
if (t == 0)
ans += W[i]->f;
else
T[t] = true;
}

printf("%d\n", ans);
}

因为不同的任务不能准时完成时具有不同的扣款权数，而且是最优解问题，所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢？应该放在第k个时段，因为放在1～k任意一个位置，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔到最大的一个空时间段，这样必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的，具体实现请参考下面的程序

var i,j,k,n,s,m:longint; boo:boolean; a,b:array[1..10000] of longint; hash:array[1..1000000] of boolean;procedure sort;var p,q:longint; begin for i:=1 to n-1 do for j:=i+1 to n do if b[i]

H2O
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=505;
int d[maxn],w[maxn],tim[maxn]={0};
int n,ans=0;

void shu()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&d[i]);
for(int i=1;i<=n;++i)scanf("%d",&w[i]);
}

int main()
{
shu();
int maxx=1,maxe;
for(int i=1;i<=n;++i)
{
maxx=1;
for(int j=2;j<=n;++j)
{
if(w[maxx]<=w[j])maxx=j;
}
maxe=d[maxx];
while(tim[maxe]==1)
{
maxe-=1;
}
if(maxe==0)
{
ans+=w[maxx];
}
else
{
tim[maxe]=1;

}
w[maxx]=0;
}
printf("%d",ans);
return 0;
}
```

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxa 510
using namespace std;
int u[maxa];
struct Node
{
int d,w;
}q[maxa];
bool comp(Node a,Node b)
{
return a.w>b.w;
}
int main()
{
int n,i,ans=0,sum=0,j;
memset(u,0,sizeof(u));
cin>>n;
for(i=0;i<n;++i)
cin>>q[i].d;
for(i=0;i<n;++i)
{cin>>q[i].w;sum+=q[i].w;
}
sort(q,q+n,comp);
for(i=0;i<n;++i)
{
for(j=q[i].d-1;j>=0;--j)
{
if(u[j]==0)
{
ans+=q[i].w;
u[j] = 1;
break;
}
}
}
cout<<sum-ans<<endl;
return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 500 + 10;

int used[MAXN];

struct Rw{
int d, w;
bool operator < (const Rw& a)const{
return w > a.w;

}
}r[MAXN];

int main()
{
int n, ans = 0;
cin>>n;
for(int i = 1; i <= n; i++)
cin>>r[i].d;
for(int i = 1; i <= n; i++)
cin>>r[i].w;
sort(r+1, r+1+n);
for(int i = 1; i <= n; i++){
int bigflag = 1;
for(int j = r[i].d - 1; j >= 0; j--)
if(!used[j]){
used[j] = 1;
bigflag = 0;
break;
}
if(bigflag) ans += r[i].w;
}
cout<<ans;
return 0;
}
贪心

方晨羽——福利站（pascal）
pascal
type
node=record
t,w:longint;
end;
var
i,n,ans,j:longint;
a:array[0..501] of node;
flag:array[0..501] of boolean;
f:boolean;
temp:node;
begin
readln(n);
for i:=1 to n do read(a[i].t);
readln;
for i:=1 to n do read(a[i].w);
readln;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i].w<a[j].w
then
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
end;
fillchar(flag,sizeof(flag),true);
for i:=1 to n do
begin
f:=true;
for j:=a[i].t downto 1 do
if flag[j]
then
begin
f:=false;
flag[j]:=false;
break;
end;
if f
then
begin
for j:=n downto a[i].t do
if flag[j]
then
begin
f:=false;
flag[j]:=false;
break;
end;
inc(ans,a[i].w);
end;
end;
writeln(ans);
end.

冒泡排序+贪心算法=秒过！！！

###Algorithm:
1.按照惩罚大小降序排列
2.排序后，从前到后对于每一个任务，选择**尽量接近**它截止时间的时刻进行工作，将该时刻置为**用过**，如果发现某个任务截止时间前的每一个时刻都已经用过了，就说明无法完成，加进ans。

*可以证明此贪心策略是正确的

###Code(C++):

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 555
struct node{
int date, val;
}work[maxn];
int n, sum;
bool done[maxn];

bool cmp(node a, node b){
return a.val>b.val;
}

int main(){
cin>>n;
for(int i=1; i<=n; i++)
cin>>work[i].date;
for(int i=1; i<=n; i++)
cin>>work[i].val;
sort(work+1, work+n+1, cmp);
for(int i=1; i<=n; i++)
{
int j;
for(j=work[i].date; j; j--)
if(!done[j]){
done[j]=1;
break;
}
if(!j)
sum += work[i].val;
}
cout<<sum<<endl;
}

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 516 KiB, score = 20

测试数据 #1: Accepted, time = 0 ms, mem = 516 KiB, score = 20

测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 20

测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 20

测试数据 #4: Accepted, time = 0 ms, mem = 516 KiB, score = 20

Accepted, time = 0 ms, mem = 516 KiB, score = 100

type node=record
t,w:longint;
end;
var i,n,ans,j:longint;
a:array[0..501] of node;
flag:array[0..501] of boolean;
f:boolean;
temp:node;
begin
readln(n);
for i:=1 to n do read(a[i].t);readln;
for i:=1 to n do read(a[i].w);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i].w<a[j].w then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
end;
fillchar(flag,sizeof(flag),true);
for i:=1 to n do
begin
f:=true;
for j:=a[i].t downto 1 do
if flag[j] then begin f:=false;flag[j]:=false;break;end;
if f then
begin
for j:=n downto a[i].t do
if flag[j] then begin f:=false;flag[j]:=false;break;end;
inc(ans,a[i].w);
end;
end;
writeln(ans);
end.
水题一边过！冒泡+贪心=秒杀！

题目来自算法导论上讲拟阵（矩阵胚）实例的那一节，题目一模一样

最优解法参见算导贪心法思考题最后一题[那里写的比较全]

简单说思路：

把任务按照惩罚从大到小排序（若惩罚一样那么期限我不太清楚，我按照从大到小排AC了，因为pair类型就是这么排的。。。觉得可能无所谓吧）

列一个时间槽，第i个槽是截止到时刻i的单位时间（比如槽1是0~1时间，槽4是3~4时间）

然后检查第i个任务的限时所在时间槽及其以前是否有空缺，如果有把该任务安排在从——限时所在时间槽——向——槽1——这个方向看最接近限时所在时间槽（可以是这个槽）的时间槽内（也就是完成了任务的安排）；如果没有那么从最后往前看找最晚的空缺安排上去，并且增加惩罚值

证明采用拟阵（矩阵胚）理论，参见算法导论（算法艺术与信息学竞赛学习指导的证明中第152页的引理中第二条>=符号打错了应该是

VijosNT Mini 2.0.5.7 Special for Vijos

foo.pas(37,6) Warning: Variable "sum" does not seem to be initialized

├ 测试数据 01：答案正确... (17ms, 588KB)

├ 测试数据 02：答案正确... (44ms, 588KB)

├ 测试数据 03：答案正确... (28ms, 588KB)

├ 测试数据 04：答案正确... (32ms, 588KB)

├ 测试数据 05：答案正确... (17ms, 588KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 140ms / 588KB

program jinpengisasuperman;

var

a,b,c,d,sum ,i,j,k:longint ;

x,y,z:array[0..500] of longint;

bo:boolean;

begin

readln(a);

for i:=1 to a do read(x[i]); readln;

for j:=1 to a do read(y[j]); readln;

d:=1;

repeat

begin

bo:=true;

for i:=1 to a-d do if y[i]0) do

c:=c-1;

if c>0 then

z[c]:=y[i];

end;

for i:= 1 to a do

sum:=sum+y[i];

for i:=1 to a do

sum:=sum-z[i];

write(sum);

end.

最最最最最最最最最最最最最最最最最最最最最最最最最最最朴素代码！！！

一点儿无优化！！！

不秒杀！！！

水题用水程！！！

ＭＡＧＩＣ２０１３！！

program p1604;

type re=record

　　 time:integer;

　　 w:integer;

　　 end;

var i,j,k:longint;

a:array[1..500] of re;

b:array[1..500] of longint;

sum,n:longint;

procedure kp(l,r:longint);

var i,j,x,t:longint;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2].w;

repeat

while a[i].w>x do inc(i);

while a[j].w

事实上这是一道很难的语文翻译题

翻译一下就是：给你N个任务，让你在1，2，.....到N这N个时间点每个时间点完成一个任务，完成的顺序由你来排。如果有任务不能在小于等于读入的时间点上完成，那么就加一个对应的数到Ans中。你的目的就是要用一种安排方式找到最小的Ans，并输出这个结果。

方法就是很简单的排序+贪心+Boolean模拟了。

水至极致...

呃.....

#include

int n;

int limit[501],give[501],time[501]={};

int main()

{

int i,j;

scanf("%d",&n);

for(i=1;i

终于看到水题了

热泪盈眶~~~~

水题

样例打错了，我还以为程序写错了