1512.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1512 on 2006-07-23 at 15:40:24 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 102400;
const int INF = 2100000000;

class Sequence {
public:
	int o, v;
	bool operator <(const Sequence& s) const { return v < s.v; }
};

inline int dis(int, int);

int main()
{
	int n, k, p, t;
	int i;
	Sequence s[MAX];
	
	while(scanf("%d %d", &n, &k) != EOF && n != 0) {
		s[0].v = s[0].o = 0; n++;
		for(i = 1; i < n; i++) {
			scanf("%d", &p);
			s[i].v = s[i-1].v + p;
			s[i].o = i;
		}
		sort(s, s+n);
		for(i = 0; i < k; i++) {
			scanf("%d", &t);
			int l = 0, u, bl, bu;
			int best = INF, bs;
			for(u = 1; u < n; u++) {
				while(l+1 != u && dis(t, s[u].v-s[l].v) >= dis(t, s[u].v-s[l+1].v)) {
					l++;
				}
				int cur = dis(t, s[u].v-s[l].v);
				if(cur < best) {
					best = cur;
					bs = abs(s[u].v-s[l].v);
					bl = s[u].o > s[l].o ? (s[l].o+1) : (s[u].o+1);
					bu = s[u].o < s[l].o ? s[l].o : s[u].o;
				}
			}
			printf("%d %d %d\n", bs, bl, bu);
		}
	}
	
	return 0;
}

inline int dis(int a, int b)
{
	int x = abs(a), y = abs(b);
	return abs(x-y);
}