題目背景

計(jì)算機(jī)競賽小組的神牛V神終于結(jié)束了萬惡的高考，然而作為班長的他還不能閑下來，班主任老t給了他一個(gè)艱巨的任務(wù)：幫同學(xué)找出最合理的大學(xué)填報(bào)方案。可是v神太忙了，身后還有一群小姑娘等著和他約會(huì)，于是他想到了同為計(jì)算機(jī)競賽小組的你，請(qǐng)你幫他完成這個(gè)艱巨的任務(wù)。

題目描述

根據(jù)n位學(xué)生的估分情況，分別給每位學(xué)生推薦一所學(xué)校，要求學(xué)校的預(yù)計(jì)分?jǐn)?shù)線和學(xué)生的估分相差最小（可高可低，畢竟是估分嘛），這個(gè)最小值為不滿意度。求所有學(xué)生不滿意度和的最小值。讀入數(shù)據(jù)有三行，第一行讀入兩個(gè)整數(shù)m,n。m表示學(xué)校數(shù)，n表示學(xué)生數(shù)。第二行共有m個(gè)數(shù)，表示m個(gè)學(xué)校的預(yù)計(jì)錄取分?jǐn)?shù)。第三行有n個(gè)數(shù)，表示n個(gè)學(xué)生的估分成績。輸出數(shù)據(jù)有一行，為最小的不滿度之和。

輸入輸出格式

輸入格式：

?

輸出格式：

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 4 3 513 598 567 689 500 600 550 輸出樣例#1：?復(fù)制 32

說明

數(shù)據(jù)范圍：對(duì)于30%的數(shù)據(jù)，m，n<=1000,估分和錄取線<=10000;對(duì)于100%的數(shù)據(jù)，n,m<=100,000,錄取線<=1000000。

?

又是一個(gè)做了好久的題。。

?

剛開始，

就直接一個(gè)一個(gè)求差，取最小值相加。。

?

t的很慘，

代碼：

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<map> 7 #include<queue> 8 using namespace std; 9 10 int n,m,x,ans; 11 int sch[100002],stu[100002],cha[100002]; 12 13 int abss(int x,int y) 14 { 15 if(x>y) return x-y; 16 else return y-x; 17 } 18 19 int main() 20 { 21 scanf("%d%d",&m,&n); 22 for(int i=1;i<=m;++i) 23 scanf("%d",&sch[i]); 24 for(int i=1;i<=n;++i) 25 scanf("%d",&stu[i]); 26 memset(cha,0x7f,sizeof(cha)); 27 for(int i=1;i<=n;++i) 28 { 29 for(int j=1;j<=m;++j) 30 { 31 x=abss(stu[i],sch[j]); 32 cha[i]=min(cha[i],x); 33 } 34 ans+=cha[i]; 35 } 36 printf("%d",ans); 37 return 0; 38 } 30T

?

?

?

然后，，，

經(jīng)過一番討論，，

想到了一種貪心思路，，

小格格太強(qiáng)了，，雖然是簡單題，

但這種思路，，，打死我也想不到、、、

?

思路：先都排一遍序，

然后求差比較相鄰的差，

重點(diǎn)！：

如果后面的差比前面的大，

那么后面的后面的肯定也比前面的大，

那就一定是前面這個(gè)的差最小，

加上，break掉就好了，

如果前面的比后面的大，，那就繼續(xù)。

?

哇塞！！好像也不是很難。。。

?

然后最后一個(gè)要單獨(dú)處理。

?

代碼：

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<map> 7 #include<queue> 8 using namespace std; 9 10 int n,m,x1,x2,ans,k=2; 11 int sch[100002],stu[100002]; 12 13 int abss(int x,int y) 14 { 15 if(x>y) return x-y; 16 else return y-x; 17 } 18 19 int main() 20 { 21 scanf("%d%d",&m,&n); 22 for(int i=1;i<=m;++i) 23 scanf("%d",&sch[i]); 24 sort(sch+1,sch+m+1); 25 for(int i=1;i<=n;++i) 26 scanf("%d",&stu[i]); 27 sort(stu+1,stu+n+1); 28 for(int i=1;i<=n;++i) 29 { 30 for(int j=k; j<=m; ++j) 31 { 32 k=j; 33 x2=abss(sch[j],stu[i]); 34 x1=abss(sch[j-1],stu[i]); 35 if(x2>x1) 36 { 37 ans+=x1; 38 break; 39 } 40 if(k==m) ans+=abss(sch[m],stu[i]); 41 } 42 } 43 printf("%d",ans); 44 return 0; 45 }

?

---

如果你不開心，那我就把右邊這個(gè)帥傻子分享給你吧，?

你看，他這么好看，那么深情的望著你，你還傷心嗎？?

真的！這照片盯上他五秒鐘就想笑了。?

一切都會(huì)過去的。

轉(zhuǎn)載于:https://www.cnblogs.com/Mary-Sue/p/9433807.html

總結(jié)

以上是生活随笔為你收集整理的P1678 烦恼的高考志愿的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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