TZOJ3326--Barn Repair(优先队列，贪心)

标签：Repair const -- 牛棚 房间 负数 int TZOJ3326

题目简述：

 

某天刮了一阵大风，把牛棚的门吹飞了，总共有s个牛棚，幸运的是并不是每个牛棚都有牛。现在你可以购买m块木板，商店里有各种型号的木板，木板长度为多少就需要多少金钱。木板用来给牛棚装上门。要求把所有有牛的牛棚都装上门，并且花的金钱最少。

给了一正整数C，接下来C行每行一个正整数，表示该牛棚有牛。

标准输入：

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

标准输出：

25

思路：

把输入转换一下，就是有50个房间，编号为1-50，其中18个房间为有牛的房间，连续无牛的房间连起来，有牛的房间连起来。

无牛的房间用负数来表示，有牛的房间用正数来表示

可以得到如下数组

-2 2 -1 1 -1 1 -5 4 -3 1 -3 3 -2 2 -8 4 -7 可以发现这个数组有8个正整数区间，然而m=4，所以需要把正数区间合并，也就是选择一个负数把其左右正数合在一起，这样所选的房间数就要加上这个负数。 最后贪心选择负数即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
 4 #define int long long
 5 const int N=1e5+7;
 6 const int P=131;
 7 const int LINF=1e13+7;
 8 const int MOD=998244353;
 9 bool C=0;
10 int a[N];
11 void solve(){
12     int n,m,c;
13     cin>>n>>m>>c;
14     vector<int> v;
15     for(int i=1;i<=c;i++){
16         int x;
17         cin>>x;
18         a[x]=1;
19     }
20     int len=1;
21     for(int i=1;i<=m;i++){
22         if(a[i]==a[i-1]) len++;
23         else{
24             if(a[i]==1)
25                 v.push_back(-len);
26             else v.push_back(len);
27             len=1;
28         }
29     }
30     if(a[m]==1) v.push_back(len);
31     priority_queue<int> q;
32     int sum=0;
33     int res=0;
34     for(int i=0;i<(int)v.size();i++){
35         if(i==0&&v[i]<0) continue;
36         if(v[i]<0) q.push(v[i]);
37         else{
38             sum++;
39             res+=v[i];
40         }
41     }
42     sum-=n;
43     while(sum>0){
44         if(q.empty()) break;
45         res-=q.top();
46         q.pop();
47         sum--;
48     }
49     cout<<res<<endl;
50 
51 }
52 signed main(){
53     IOS;
54     int t;
55     if(C) cin>>t;
56     else t=1;
57     while(t--) solve();
58 }
59 /*
60 4
61 -2 2 -1 1 -1 1 -5 4 -3 1 -3 3 -2 2 -8 4 -7
62 6-5 4 -3 1 -3 3 -2 2 -8 4
63 6-5 4 -3 1 -3 7 -8 4
64 6-5 8 -3 7 -8 4
65 */

 

标签：Repair,const,--,牛棚,房间,负数,int,TZOJ3326
From： https://www.cnblogs.com/Feintl/p/17625342.html