題目背景
計(jì)算機(jī)競(jìng)賽小組的神牛V神終于結(jié)束了萬(wàn)惡的高考，然而作為班長(zhǎng)的他還不能閑下來(lái)，班主任老t給了他一個(gè)艱巨的任務(wù)：幫同學(xué)找出最合理的大學(xué)填報(bào)方案。可是v神太忙了，身后還有一群小姑娘等著和他約會(huì)，于是他想到了同為計(jì)算機(jī)競(jìng)賽小組的你，請(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é)生的估分成績(jī)。輸出數(shù)據(jù)有一行，為最小的不滿度之和。

輸入輸出格式
輸入格式：
輸出格式：
輸入輸出樣例
輸入樣例#1：
4 3
513 598 567 689
500 600 550
輸出樣例#1：
32
說(shuō)明
數(shù)據(jù)范圍：對(duì)于30%的數(shù)據(jù)，m，n<=1000,估分和錄取線<=10000;對(duì)于100%的數(shù)據(jù)，n,m<=100,000,錄取線<=1000000。
.
.
.
.
.
.

分析

如果a[mid]，即錄取分?jǐn)?shù)線數(shù)組中的第mid個(gè)元素小于或等于那位同學(xué)的分?jǐn)?shù)，mid+1賦值給l，否則，mid賦值給r。

最后查找完后，那么求錄取分?jǐn)?shù)線數(shù)組中的第l-1個(gè)元素和錄取分?jǐn)?shù)線數(shù)組中的第l個(gè)元素他們兩與那位同學(xué)的估分的絕對(duì)值，那么答案就累加兩個(gè)絕對(duì)值中最小的。
.
.
.
.
.

程序：

#include<iostream> #include<cmath> #include<algorithm> using namespace std; int m,n,a[1000010],b[1000010];int main() {cin>>m>>n;for (int i=1;i<=m;i++)cin>>a[i];sort(a+1,a+m+1);for (int i=1;i<=n;i++)cin>>b[i];int ans=0;for (int i=1;i<=n;i++){int l=0,r=m+1;while (l<r){int mid=(l+r)/2;if (a[mid]<=b[i]) l=mid+1; else r=mid;}if (b[i]<=a[1]) ans+=a[1]-b[i];else ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));}cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499909.html

總結(jié)

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

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