2045 - 线段覆盖

一段长度为s的数轴，每一个单位长度为一个空格，其中有c个空格占有物品。

东神想用不超过m个线段覆盖这些物品，每个线段长度不限。东神希望使用的线段的总长度最小，请你帮忙求出需要线段的最小总长度

数据样例如图

Input

数据有多组，以EOF结束

每组第一行有三个整数m,s,c.以空格隔开。线段的最大数量m(1<= m<=50)数轴长度s(1<= s<=200)物品的数量c(1 <= c <=c)

接下来有c行，每行有一个整数number，代表一个物品的位置(1 <= number <= S)

Output

每组数据输出一个整数占据一行，代表需要的线段最小总长度

Examples

Input

Output

Solution C

#include <stdio.h>
#include <string.h>

int main(){
	
	int m, s, c, i, j, k, number, tmp, flag, min, max, result,
		goods[256], notOccupied[256];
	
	while (EOF != scanf("%d%d%d", &m, &s, &c)){
		
		min = 256;
		max = 0;
		memset(goods, 0, sizeof(goods));
		while (c--){
			
			scanf("%d", &tmp);
			
			goods[tmp] = 1;
			if (tmp > max){
				max = tmp;
			}
			if (tmp < min){
				min = tmp;
			}
		}
		
		k = 0;
		tmp = 0;
		flag = 0;
		for (i = min; i <= max; i++){
			
			if (goods[i]){
				if (flag){
					notOccupied[k++] = tmp;
				}
				tmp = 0;
				flag = 0;
				continue;
			}
			
			tmp++;
			flag = 1;
		}
		
		for (i = 0; i < k; i++){
			
			for (j = i + 1; j < k; j++){
				
				if (notOccupied[i] < notOccupied[j]){
					tmp = notOccupied[i];
					notOccupied[i] = notOccupied[j];
					notOccupied[j] = tmp;
				}
			}
		}
		
		result = max - min + 1;
		
		for (i = 0; i < m - 1 && i < k; i++){
			
			result -= notOccupied[i];
		}
		
		printf("%d\n", result);
	}
	
	return 0;
}

Solution C++

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int V = 200 + 5;
int m, s, c, len[V], ans[V];
int main() {
    int i, j;
    while(~scanf("%d%d%d", &m, &s, &c)) {
        for(i = 0; i < c; ++i)
            scanf("%d", &len[i]);
        sort(len, len + c);
        for(i = 1; i < c; ++i)
            ans[i - 1] = len[i] - len[i - 1] - 1;
        sort(ans, ans + c - 1);
        int L = len[c - 1] - len[0] + 1;
        while(--m && c--)
            L -= ans[c - 1];
        printf("%d\n", L);
    }
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题