NC15945. 新田忌赛马
描述
例如：当有n=3匹马的时候
齐威王三匹马的速度为40, 30, 20
三匹马对应的刀币值为 1，2，3
田忌三匹马的速度为 20，30，50
齐威王的马顺序固定，田忌可以随意调动马匹出场顺序
当田忌出场顺序为 20，50，30 的时候
田忌会先失去一个刀币，再获得两个刀币，再获得三个刀币，故最后田忌赢得四个刀币，输出4，如果输了x个刀币就输出x的负数。输入描述
输入第一行包含一个整数T，代表测试案例个数。（5<=T<=10）
接下来每个测试案例都包括四行
第一行为一个整数n（0<n<=1000），代表马的个数。
第二行为n个整数，代表齐威王各匹马的速度。
第三行为n个整数，代表齐威王各匹马的刀币值（0<刀币值<=100），与速度值一一对应。
第四行为n个整数，代表田忌各匹马的速度。（0<速度值<=100）
输出描述
输出田忌最多可以赢得的刀币值。
示例1
输入:
2 3 40 30 20 1 2 3 20 30 50 5 25 25 50 60 10 10 50 5 100 30 70 5 30 25 40
输出:
4 185
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 404K, 提交时间: 2020-07-29 12:54:25
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int t,n;
multiset<int> st;
int v[N],w[N];
int main() {
int i,j,x,ans;
cin>>t;
while (t--) {
cin>>n; st.clear();
for (i=1;i<=n;i++) cin>>v[i];
for (i=1;i<=n;i++) cin>>w[i];
for (i=1;i<=n;i++) {
cin>>x;
st.insert(x);
}
ans=0;
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if (w[i]<w[j]) {
swap(w[i],w[j]);
swap(v[i],v[j]);
}
for (i=1;i<=n;i++) {
// cout<<v[i]<<endl;
auto p=st.upper_bound(v[i]);
if (p==st.end()) {
st.erase(st.begin());
ans-=w[i];
}
else {
st.erase(p);
ans+=w[i];
}
}
cout<<ans<<endl;
}
}
C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 348K, 提交时间: 2020-11-16 16:41:16
#include<bits/stdc++.h>
using namespace std;
const int nx=1e3+5;
struct node{
int v,m;
bool operator < (const node&oth)const{return m>oth.m;}
}p[nx];
int b[nx],n,t;
bool vs[nx];
int main(){
scanf("%d",&t);
while(t--){
memset(vs,0,sizeof vs);
scanf("%d",&n);
for(int i=0;i<n;++i)scanf("%d",&p[i].v);
for(int i=0;i<n;++i)scanf("%d",&p[i].m);
for(int i=0;i<n;++i)scanf("%d",b+i);
sort(p,p+n),sort(b,b+n);
int ans=0;
for(int i=0;i<n;++i){
int t=upper_bound(b,b+n,p[i].v)-b;
while(vs[t])++t;
if(t==n)ans-=p[i].m;
else ans+=p[i].m,vs[t]=1;
}
printf("%d\n",ans);
}
}