首页 > itarticle > pat甲级1044

pat甲级1044

admin 11月 11, 2020 0

1044 Shopping in Mars (25 point(s))

原地址

思路：

直接枚举O(n^2),超时。
这里利用前缀和数组 sum[j-1] - sum[i-1] = s,转化为sum[j-1] = sum[i-1] + s。
这样就可以二分查找所有满足的sum[j-1]。

我踩的坑点：

对二分理解的不够透彻（查找第一个大于num的元素位置，然后减一.所以要注意二分的上界）
对前缀和数组理解的也不够透彻

代码:


using namespace std;
const int maxn = 1e5+5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int MOD = 1000000007;
typedef long long ll;
#define pb push_back

int a[maxn];

int () {
#ifdef ONLIGE_JUDGE
#else
    freopen("H:\in.txt","r",stdin);
#endif 
	int n,m,t = INF;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		scanf("%d",&a[i]),a[i] += a[i-1];
	for (int i = 1; i <= n; ++i) {
		int j = upper_bound(a+i,a+n+1,a[i-1]+m) - a; 
		if (a[j-1] - a[i-1] == m) {//a[j-1] may be the ans;
			t = m;
			break;
		} else if ( j <= n && a[j] - a[i-1] < t)
			t = a[j] - a[i-1];	
	}
	for (int i = 1; i <= n; ++i) {
		int j = upper_bound(a+i,a+n+1,a[i-1]+t) - a;
		if (a[j-1] - a[i-1] == t)
			printf("%d-%dn",i,j-1);
	}
	return 0; 
}