LOJ#10001. 「一本通 1.1 例 2」种树

内存限制：512 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： 1bentong

提交提交记录统计讨论测试数据

某条街被划为

第一行为

第二行为

下面

输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。

样例输入

样例输出

$30%30\%30% 的数据满足 0<n≤1000,0<h≤5000<n\le 1000, 0<h\le 5000<n≤1000,0<h≤500；$

$100%100\%100% 的数据满足 0<n≤3×104,h≤5000,0<b≤e≤3×104,r≤eb+10<n\le 3\times 10^4, h\le 5000, 0<b\le e\le 3\times 10^4, r\le e-b+10<n≤3×104,h≤5000,0<b≤e≤3×104,r≤eb+1。$

 1 //2018-07-27 20:59:54
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int N = 300001;
 8 int n, h;
 9 struct node{
10     int st, ed, v;
11 }a[5001];
12 
13 int ans, k, used[N];
14 
15 bool cmp(node a, node b){
16     return a.ed < b.ed;
17 }
18 
19 int main(){
20     scanf("%d%d", &n, &h);
21     for(int i=1; i<=h; i++)
22         scanf("%d%d%d", &a[i].st, &a[i].ed, &a[i].v);
23     sort(a+1, a+h+1, cmp);
24     
25     for(int i=1; i<=h; i++){
26         k = 0;
27         for(int j=a[i].st; j<=a[i].ed; j++){
28             if(used[j]) k++; 
29         }
30         if(k >= a[i].v) continue;
31         for(int j=a[i].ed; j>=a[i].st; j--){
32             if(!used[j]){
33                 used[j] = 1;
34                 k++;
35                 ans++;
36                 if(k >= a[i].v) break;
37             }
38         }
39     }
40         
41     printf("%d\n", ans);
42 
43     return 0;
44 }

转载于:https://www.cnblogs.com/sineagle/p/9379699.html

LOJ#10001. 「一本通 1.1 例 2」种树

#10001. 「一本通 1.1 例 2」种树

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示