关键词：
题目描述
Farmer John has built a sand castle! Like all good castles, the walls have crennelations, that nifty pattern of embrasures (gaps) and merlons (filled spaces); see the diagram below. The N (1 <= N <= 25,000) merlons of his castle wall are conveniently numbered 1..N; merlon i has height M_i (1 <= M_i <= 100,000); his merlons often have varying heights, unlike so many.
He wishes to modify the castle design in the following fashion: he has a list of numbers B_1 through B_N (1 <= B_i <= 100,000), and wants to change the merlon heights to those heights B_1, ..., B_N in some order (not necessarily the order given or any other order derived from the data).
To do this, he has hired some bovine craftsmen to raise and lower the merlons‘ heights. Craftsmen, of course, cost a lot of money. In particular, they charge FJ a total X (1 <= X <= 100) money per unit height added and Y (1 <= Y <= 100) money per unit height
reduced.
FJ would like to know the cheapest possible cost of modifying his sand castle if he picks the best permutation of heights. The answer is guaranteed to fit within a 32-bit signed integer.
Note: about 40% of the test data will have N <= 9, and about 60% will have N <= 18.
约翰用沙子建了一座城堡．正如所有城堡的城墙，这城墙也有许多枪眼，两个相邻枪眼中间那部分叫作“城齿”． 城墙上一共有N(1≤N≤25000)个城齿，每一个都有一个高度Mi.(1≤Mi≤100000)．现在约翰想把城齿的高度调成某种顺序下的Bi，B2，…，BN(1≤Bi≤100000). -个城齿每提高一个单位的高度，约翰需要X(1≤X≤100)元；每降低一个单位的高度，约翰需要Y(1≤y≤100)元． 问约翰最少可用多少钱达到目的．数据保证答案不超过2^31-1．
输入输出格式
输入格式：
-
Line 1: Three space-separated integers: N, X, and Y
- Lines 2..N+1: Line i+1 contains the two space-separated integers: M_i and B_i
输出格式：
- Line 1: A single integer, the minimum cost needed to rebuild the castle
输入输出样例
说明
FJ‘s castle starts with heights of 3, 1, and 1. He would like to change them so that their heights are 1, 2, and 2, in some order. It costs 6 to add a unit of height and 5 to remove a unit of height.
FJ reduces the first merlon‘s height by 1, for a cost of 5 (yielding merlons of heights 2, 1, and 1). He then adds one unit of height to the second merlon for a cost of 6 (yielding merlons of heights 2, 2, and 1).
思路：贪心
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 25010 using namespace std; int n,x,y,ans; int m[MAXN],b[MAXN]; int main(){ scanf("%d%d%d",&n,&x,&y); for(int i=1;i<=n;i++) scanf("%d%d",&m[i],&b[i]); sort(m+1,m+1+n); sort(b+1,b+1+n); for(int i=1;i<=n;i++){ if(m[i]>b[i]) ans+=(m[i]-b[i])*y; else if(m[i]<b[i]) ans+=(b[i]-m[i])*x; } cout<<ans; }
洛谷p2946[usaco09mar]牛飞盘队cowfrisbeeteam
洛谷P2946[USACO09MAR]牛飞盘队CowFrisbeeTeam动态规划1#include<cstdio>2#include<cmath>3#include<cstdlib>4#include<cstring>5#include<iostream>6#include<iomanip>7#include<algo 查看详情
洛谷2944[usaco09mar]地震损失2earthquakedamage2
https://www.luogu.org/problem/show?pid=2944题目描述WisconsinhashadanearthquakethathasstruckFarmerJohn‘sfarm!Theearthquakehasdamagedsomeofthepasturessothattheyareunpassable.Remarkably,noneofthecowpathswasd 查看详情
洛谷p2904[usaco08mar]跨河rivercrossing
P2904[USACO08MAR]跨河RiverCrossing题目描述FarmerJohnisherdinghisNcows(1<=N<=2,500)acrosstheexpansesofhisfarmwhenhefindshimselfblockedbyariver.Asingleraftisavailablefortransportation.FJknowsthathemustr 查看详情
洛谷p2904[usaco08mar]跨河rivercrossing
题目描述FarmerJohnisherdinghisNcows(1<=N<=2,500)acrosstheexpansesofhisfarmwhenhefindshimselfblockedbyariver.Asingleraftisavailablefortransportation.FJknowsthathemustrideontheraftforallcrossingsandth 查看详情
洛谷2115[usaco14mar]破坏sabotage
https://www.luogu.org/problem/show?pid=2115题目描述FarmerJohn‘sarch-nemesis,FarmerPaul,hasdecidedtosabotageFarmerJohn‘smilkingequipment!ThemilkingequipmentconsistsofarowofN(3<=N<=100,000)milkingmach 查看详情
洛谷p3079[usaco13mar]农场的画farmpainting
P3079[USACO13MAR]农场的画FarmPainting题目描述Afterseveralharshwinters,FarmerJohnhasdecideditistimetore-painthisfarm.ThefarmconsistsofNfencedenclosures(1<=N<=50,000),eachofwhichcanbedescribedbyarectangle 查看详情
[usaco07mar]黄金阵容均衡goldbalancedl…(洛谷1360）
题目描述FarmerJohn‘sNcows(1≤N≤100,000)sharemanysimilarities.Infact,FJhasbeenabletonarrowdownthelistoffeaturessharedbyhiscowstoalistofonlyKdifferentfeatures(1≤K≤30).Forexample,cowsexhibitingfeature#1mighth 查看详情
洛谷——p2904[usaco08mar]跨河rivercrossing
https://www.luogu.org/problem/show?pid=2904题目描述FarmerJohnisherdinghisNcows(1<=N<=2,500)acrosstheexpansesofhisfarmwhenhefindshimselfblockedbyariver.Asingleraftisavailablefortransportation.FJknows 查看详情
洛谷p2986[usaco10mar]greatcowgat…(树形dp+容斥原理)
P2986[USACO10MAR]伟大的奶牛聚集GreatCowGat…题目描述BessieisplanningtheannualGreatCowGatheringforcowsallacrossthecountryand,ofcourse,shewouldliketochoosethemostconvenientlocationforthegatheringtotakeplace. 查看详情
洛谷p3019[usaco11mar]会见点meetingplace
题目背景征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。题目描述BessieandJonellaregreatfriends.SinceFarmerJohnscrambleswherethecowsgrazeeveryday,theyaresometimesquitefarfromeachotherandcan‘ttalk.ThepasturesandpathsonFJ‘sfa 查看详情
洛谷p1849[usaco12mar]拖拉机tractor
题目描述Afteralongdayofwork,FarmerJohncompletelyforgotthathelefthistractorinthemiddleofthefield.Hiscows,alwaysuptonogood,decidetoplayaprankofFarmerJohn:theydepositNbalesofhay(1<=N<=50,000)atvariousl 查看详情
洛谷p2903[usaco08mar]麻烦的干草打包机theloathesomehaybaler
P2903[USACO08MAR]麻烦的干草打包机TheLoathesomeHayBaler题目描述FarmerJohnhaspurchasedtheworld‘smostloathesomehaybaler.Insteadofhavingadrive-rollerthatdrivesmaybeanidlerrollerthatdrivesthepowertake-offforthebaler,i 查看详情
洛谷——p2884[usaco07mar]每月的费用monthlyexpense
https://www.luogu.org/problemnew/show/P2884题目描述FarmerJohnisanastoundingaccountingwizardandhasrealizedhemightrunoutofmoneytorunthefarm.Hehasalreadycalculatedandrecordedtheexactamountofmoney(1≤moneyi 查看详情
洛谷p2900[usaco08mar]土地征用landacquisition
题目：https://www.luogu.org/problemnew/show/P2900题目描述FarmerJohnisconsideringbuyingmorelandforthefarmandhashiseyeonN(1<=N<=50,000)additionalrectangularplots,eachwithintegerdimensions(1<=width_i&l 查看详情
洛谷——p1849[usaco12mar]拖拉机tractor
https://www.luogu.org/problemnew/show/P1849题目描述Afteralongdayofwork,FarmerJohncompletelyforgotthathelefthistractorinthemiddleofthefield.Hiscows,alwaysuptonogood,decidetoplayaprankofFarmerJohn:theydepos 查看详情
洛谷p2904[usaco08mar]跨河rivercrossing动态规划
洛谷P2904[USACO08MAR]跨河RiverCrossing动态规划区间DPf[i]表示将i头牛运了过去，然后John又返回所需要的最少时间 1#include<cstdio>2#include<cstring>3#include<cmath>4#include<cstdlib>5#include<string>6#in 查看详情
洛谷p3018[usaco11mar]树装饰treedecoration
洛谷P3018[USACO11MAR]树装饰TreeDecoration树形DP因为要求最小，我们就贪心地用每个子树中的最小cost来支付就行了 1#include<bits/stdc++.h>2#defineFor(i,j,k)for(inti=j;i<=k;i++)3#defineDow(i,j,k)for(inti=j;i>=k;i--)4#defineLL 查看详情
洛谷p3052[usaco12mar]摩天大楼里的奶牛cowsinaskyscraper
P3052[USACO12MAR]摩天大楼里的奶牛CowsinaSkyscraper题目描述AlittleknownfactaboutBessieandfriendsisthattheylovestairclimbingraces.Abetterknownfactisthatcowsreallydon‘tlikegoingdownstairs.Soafterthecowsfinishracingt 查看详情