To Luogu .2242 Highway maintenance problems

Title Description

Because it hasn't been repaired for a long time ,A On the freeway of our country appeared N Pit . In order to fill the gap as soon as possible N Pit ,A The U.S. decided to M Traffic control in this area . For the convenience of solving , hypothesis A There is only one highway in China , And it's straight . Now give N The location of the pit , Please calculate , At least how far to control traffic ？

I / O format

Input format ：

There are two lines of input data , The first line is two positive integers N、M （2<=N<=15000,M<=N）. The second line gives N The coordinates of a pit （ The coordinate values are all in the long integer range , From small to large , And there won't be two points with the same coordinates ）.

Output format ：

Just one line , Is the minimum length and .

I/o sample

sample input #1： 

18 4

3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43
sample output #1： 

25

explain

[ Sample explanation ]

The traffic control areas are ：3-8,14-21,25-31,40-43.

Code ：

 #include<cstdio>

#include<algorithm>

using namespace std;
int n,m,num,last,Ans,Delta[];
int main()

{

scanf("%d%d",&n,&m);

for(int i=;i<=n;i++)

{

scanf("%d",&num);

Delta[i]=num-last;

last=num;

}

//n Number There is n-1 An interval , It can be used m-1 individual 0 Fill in the biggest gap ,

// Add the rest . Because each segment includes two ends (a-b+1), Less calculation 1, So at the end of the day m

/*for(int i=1;i<=n;i++)

printf("%d:%d\n",i,Delta[i]);*/

sort(Delta+,Delta++n);// Remove the first element from 0 Distance between 

for(int i=;i<=n-m+;i++)// Ignore Delta[1]

Ans+=Delta[i];

printf("%d",Ans+m);

return ;

}

Luogu P2242 More articles on road maintenance

  1. Luogu P2242 Highway maintenance problems

    P2242 Highway maintenance problems Title Description Because it hasn't been repaired for a long time ,A On the freeway of our country appeared N Pit . In order to fill the gap as soon as possible N Pit ,A The U.S. decided to M Traffic control in this area . For the convenience of solving , hypothesis A There is only one highway in China , And it's straight . ...

  2. Luogu P2242 Highway maintenance problems （Road）

    Title Description On a dark night, the wind is high , A stormy night ,farmer John The roof of the cattle shed . The door blew away . Fortunately, many cows are on holiday , So the cowshed is not full . The cowshed is lined up one next to the other , Cows live in it for the night . Some cowsheds have cattle ...

  3. Luogu P1265 Highway construction （Prim）

    To Luogu .1265 Highway construction Title Description A state n Cities , There is no road between them , So the traffic is very inconvenient . To solve this problem “ On the road to ” The problem of , The government decided to build roads . The task of building roads is done by all cities . The construction work will be completed in several rounds ...

  4. Luogu P2243 Circuit maintenance [ shortest path ]

    Subject portal Circuit maintenance Background Elf Is from Gliese Girl of the planet , Drifting to the earth by accident . When she was helpless , Good transporter Mark and James Took her in .Elf Thank you very much Mark and Jam ...

  5. Luogu P1265 Highway construction

    P1265 Highway construction 177 adopt 600 Submit The user does not exist Label graph theory The difficulty is universal +/ Improve Submit the question   Discuss   Answer key   Record The latest discussion long long Type assignment -1 Why? … p The party 80 Advance Why, but ...

  6. Luogu ——P1265 Highway construction

    P1265 Highway construction Title Description A state n Cities , There is no road between them , So the traffic is very inconvenient . To solve this problem “ On the road to ” The problem of , The government decided to build roads . The task of building roads is done by all cities . The construction work was completed in several rounds . In every ...

  7. Luogu P2243 Circuit maintenance

    P2243 Circuit maintenance Background Elf Is from Gliese Girl of the planet , Drifting to the earth by accident . When she was helpless , Good transporter Mark and James Took her in .Elf Thank you very much Mark and Jam ...

  8. Luogu P1265 The problem of highway construction

    Title Description A state n Cities , There is no road between them , So the traffic is very inconvenient . To solve this problem “ On the road to ” The problem of , The government decided to build roads . The task of building roads is done by all cities . The construction work was completed in several rounds . In each round , Each city chooses one ...

  9. 【Dijkstra Heap optimization 】 Luogu P2243 Circuit maintenance

    Background Elf Is from Gliese Girl of the planet , Drifting to the earth by accident . When she was helpless , Good transporter Mark and James Took her in .Elf Thank you very much Mark and James, But I haven't been able to give ...

Random recommendation

  1. Annotation driven Spring cache Cache Introduction

    summary Spring 3.1 Introduced exciting annotation based (annotation) The cache of (cache) technology , It is not a specific cache implementation in essence ( for example EHCache perhaps OSCache), It's a cache that makes ...

  2. shell command getopts analysis

    getopts Is a statement that gets and processes command line options , The format is getopts option_string variable . among option_string Contains a valid single character option , if getopts The order is in life ...

  3. JavaScript String Support assistance format function +【 Pagination 1】

    /** ) {         && ; i < arguments.length; i++) {                 : int.Parse(Request.Par ...

  4. OC Three characteristics of object-oriented

    OC Three characteristics of object-oriented 1.OC Three characteristics of object-oriented encapsulation 1) encapsulation : In a word, it is the encapsulation of member variables . 2) It's better not to use member variables in idiom methods @public In this way, it will be directly exposed to the outside world and modified by others , The encapsulation method can also ...

  5. x64 position windows On the program development considerations

    stay Windows above 32 Bit and 64 The difference between the two positions is : 1. The difference in pointer size ,sizeof(int *) stay 32bit Here is 4 Bytes , stay 64bit Here is 8 Bytes 2.size_t The difference between ,size_t stay 32bit below ...

  6. sql Periodically migrate stored procedures for data

    create PROCEDURE [dbo].[Pro_ZT_SYS_LogInfo_clear] @dt_end datetime -- Clean up data before this date AS BEGIN SET NOCOUNT ...

  7. Out of the box VScode C++ Environmental Science

    For most people vscode To configure c++ The environment is very complicated , Here's a simple way . 1. download VSCode Official website download ( Portable version ):VSCode-win32-ia32-1.32.1.zip decompression VSCode-win ...

  8. Use spark visit hive Error log

    stay spark Execution in a cluster ./spark-shell Times the following mistakes : 18/07/23 10:02:39 WARN DataNucleus.Connection: BoneCP specified but ...

  9. [LeetCode] 133. Clone Graph_ Medium tag: BFS, DFS

    Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. OJ's ...

  10. CentOS 5/6 Necessary settings after installation （ turn ）

    explain : From the major optimization programs , It's a hodgepodge , The follow-up will be a Shell Scripts simplify operations . 1. modify ip Address . gateway . Host name .DNS etc.  ( This operation can use Setup Tools to configure , But not recommended , Too many packages , No match ...