刷题记录（NC50937 货仓选址，NC18386 字符串，NC207040 丢手绢）

NC50937 货仓选址

题目链接

关键点： 

我的第一个想法是，挑中间的点，然后画了一下，发现中间的点大概率为所有点距离的最短和

代码：

# include <iostream>
# include <algorithm>
using namespace std;
int n, sum;
int a[100000+10];
int main()
{scanf("%d", &n);for (int i=1; i<=n; i++){scanf("%d", &a[i]);}sort(a+1, a+1+n);for (int i=1; i<=n/2; i++){sum+=(a[n-i+1]-a[i]);}cout<<sum;return 0;
}

总结，对于类似的题，其实和加权的中位数相同,有两种做法：

1、直接选中间的点来计算所有的距离

2、利用前缀和，先在输入数组的时候，算出前缀和，然后先算出一个距离dist[x]（指所有点到x的距离），然后算x之后的点，

dist[x+p] = （x+p和x间的距离）*（x及其x之前的前缀和（增加的距离）-x及其x之后的前缀和（减少的距离））

NC18386 字符串

题目链接

关键点： 

1、利用尺取法，一个l指向头，一个r指向尾，r从第一个数开始，然后求当前区间的小写字母个数，一旦小写字母等于26，或者已经超过了整个的size，就退出

2、然后就是注意如何求区间字母的个数

代码：

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
string s;
int len, total;
int cnt[30];
int main()
{cin>>s;len = s.size();int r = 0;
//     cout<<len<<endl;for (int l=0; l<s.size(); l++){while (r<s.size() && total<26){int x = s[r]-'a';cnt[x]++;if (cnt[x]==1)total++;r++;}if (total==26){len = min(len, r-l);}int x = s[l]-'a';cnt[x]--;if (!cnt[x])total--;}printf("%d", len);return 0;
}

 NC207040 丢手绢

题目链接

关键点： 

1、还是尺取法，先算出所有数的和，当当前区间的和大于总和的一半时，就没有必要再算下去的，这是就退出r的循环，并且算出当前距离，并取最大值

2、还有一点，这个是个环，所以r在加一的时候，要保证r也形成个环，将数组从0开始存，然后采用以下方式，可以保证所有的数都会变成r这个右区间。

(r++)%n 

 代码：

# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
int n, sum;
int a[100000+10];
int main()
{scanf("%d", &n);for (int i=0; i<n; i++){scanf("%d", &a[i]);sum+=a[i];}int len = 0;int r = 0;int total = 0;for (int l=0; l<n; l++){while(total<sum/2){total+=a[(r++)%n];}len = max(len, min(total, sum-total));total-=a[l];}printf("%d", len);return 0;
}