注:最近这一系列ACM的内容,都是2年多之前的代码,自己回顾一下。
Plant
Submit: 1543 Accepted:426
Time Limit: 3000MS Memory Limit: 65536K
Description
又是3月12日植树节,小学一年级912班的N个小朋友手牵手跟着f老师去马路边植树,小朋友们各自的植树方案都不同,但是为了不至于相邻两棵树隔的太近,f老师留给SuperRock小朋友的任务就是找出最近两棵树之间的距离。
马路是一条长为L的线段,每个小朋友的植树方案是从x位置每隔d米植一棵树共植k棵
Input
第一行两个整数 L和N (L<=500000,N<=100000)
接下来N行每行三个整数 x,d,k (0<=x<=L, 1<=d<=L) 数据保证所有的树都在马路[0,L]之间小朋友们的植树总数至多5000000棵,至少2棵
Output
一个数,最近距离
Sample Input
20 2
5 5 2
2 7 3
Sample Output
1
Hint
一个点可能会种两棵树
Source
模拟题。为了保持内存,用的是字符数组去记录马路各个点的情况(有没有种树,种几棵了)。
最后遍历处理一下这个数组即可。如果在一个点种了两棵,那最近距离一定为0了。
#include <iostream> using namespace std; int main() { char *ch; long N, L, x, d, k, min, pos; cin >> L >> N; ch = (char *)malloc((L+5)*sizeof(char)); for (long i = 0; i <= L; i++) ch[i] = '0'; while (N--) { cin >> x >> d >> k; for (long i = x, j = 0; j < k && i <= L; j++, i+=d) { if (ch[i] == '1') ch[i] = '2'; else ch[i] = '1'; } } pos = -1; min = L + 2; for (long i = 0; i <= L; i++) { if (ch[i] == '1') { if (pos != -1 && min > i - pos) min = i - pos; pos = i; } else if (ch[i] == '2') { min = 0; break; } } cout << min << endl; // system("pause"); return 0; }