P2695 騎士的工作

題目背景

你作為一個村的村長，保衛(wèi)村莊是理所當然的了.今天，村莊里來了一只惡龍，他有n個頭，惡龍到處殺人放火。你著急了。不過天無絕人之路，現(xiàn)在來了一個騎士團。里面有m位成員（往下看）

題目描述

每個人都可以砍掉一個大小不超過（<=）z的頭，要money個金幣，求最小花費。

輸入輸出格式

輸入格式：

?

第一行兩個整數(shù) n m

下接n行，一個整數(shù) 表示n個頭的大小。

下接m行，每個人可以砍的頭大小或金幣(金幣==頭的大小）。

?

輸出格式：

?

一個整數(shù)，最小花費。如果無解，輸出“you died！”

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 2 3 5 4 7 8 4 輸出樣例#1：?復(fù)制 11

說明

1<=n,m<=20000

思路：貪心。

http://www.cnblogs.com/cangT-Tlan/p/7724179.html

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 20010 using namespace std; int n,m,pos,ans; int cost[MAXN],val[MAXN]; int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&val[i]);for(int i=1;i<=m;i++) scanf("%d",&cost[i]);sort(val+1,val+1+n);sort(cost+1,cost+1+m);for(int i=1;i<=n;i++){while(cost[++pos]<val[i]){if(pos>m){cout<<"you died!";return 0; }}ans+=cost[pos];}cout<<ans; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/8034578.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2695 骑士的工作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。