A. DIY Wooden Ladder
先找出数组中最大的两个元素a和b，b是第二大的数。答案是min(b-1，n-2)
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int arr[N];
#define min(a,b) ((a)<(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt","r",stdin);
#endif
int t;
cin>>t;
for(int ti=0; ti<t; ti++)
{
int n;
cin>>n;
int a=-1,b=-1;
for(int i=0; i<n; i++)
{
cin>>arr[i];
if(arr[i]>a)
{
b=a;
a= arr[i];
}
else if(arr[i]>b)
{
b=arr[i];
}
}
int ret = min(b-1,n-2);
if(ret<0)
ret = 0;
cout<<ret<<endl;
}
return 0;
}
B. Pillars
首先找出最大的元素，目标是将所有盘子移到
处。如果对于
，那么盘子
将无法移到柱子
。同理如果
也会导致所有盘子无法移到
处。找到最大元素
后向左向右遍历一遍即可。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2*100010;
int n;
int arr[N];
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
bool solve()
{
int ti = -1;
int t = -1;
for(int i=0;i<n;i++)
{
if(arr[i] > t)
{
t = arr[i];
ti = i;
}
}
int a = t;
for(int i=ti-1;i>=0;i--)
{
int x = arr[i];
if(x>=a)
{
return false;
}
a = min(x, a);
}
a = t;
for(int i=ti+1;i<n;i++)
{
int x = arr[i];
if(x>=a)
{
return false;
}
a=min(x,a);
}
return true;
}
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt","r",stdin);
#endif
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
if(solve())
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}
C. Array Splitting
对于分好后的第个连续子数组
，
。
当k=1时，所求答案为。
当k=2时，假设分区是1~i，i+1~n，则答案是
以此类推，答案应该为减去k-1个最大的
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3*100010;
int arr[N];
int q[N];
int n,k;
#define min(a,b) ((a)<(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt","r",stdin);
#endif
while(cin>>n>>k)
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
if(i>0)
{
q[i-1]=arr[i]-arr[i-1];
}
}
sort(q,q+n-1);
long long sum = 0;
for(int i=0;i<n-k;i++)
{
sum+=q[i];
}
cout<<sum<<endl;
}
return 0;
}
D. Yet Another Subarray Problem
设为子数组以第
个元素结尾所能得到的最佳答案。
分两种情况。考虑j>i-m，j~i的子数组的花费为best[i-m]+ \Sigma_{t=i-m+1}^i a_t - k。best[i]取两者答案的最小值。算法时间复杂度为O(nm)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3*100010;
int arr[N];
long long best[N];
int n,m,k;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt","r",stdin);
#endif
while(cin>>n>>m>>k)
{
long long ret = 0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
best[i] = max(0, arr[i]-k);
ret = max(ret,best[i]);
}
for(int i=1;i<n;i++)
{
long long t = 0;
for(int j=0;j<m &&i-j>= 0;j++)
{
t += arr[i-j];
best[i] = max(best[i], t-k);
}
if(i>=m)
{
best[i] = max(best[i], t-k+best[i-m]);
}
ret = max(best[i], ret);
}
cout<<ret<<endl;
}
return 0;
}
E. Culture
对所有数据以排序。
设，其中
表示以
所有套娃构造所能组成的最小extraspace，
表示以
所有套娃构造所能组成的满足条件的套娃数目。
倒序遍历数据，对于，找到恰好大于
的位置
，那么对于套娃
应该能装在pos-n中的某些套娃中，其extraspace应该等于
。
那么对于的计算，分三种情况。
a. 时，说明第i个套娃无法与其他套娃构造成最小extraspace，不纳入计算，
b. 时，第i个套娃应该可以构造出
个满足条件的套娃。
c. 时，
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int n;
const int N = 2*1e5+10;
pair<int, int> p[N];
pair<int, long long> dp[N];
const int mod = 1e9+7;
int main()
{
#ifdef CODEBLOCKS
freopen("in.txt", "r", stdin);
#endif // CODEBLOCKS
while(cin>>n)
{
int min_out = 0x7fffffff;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
p[i] = make_pair(b,a);
}
sort(p, p+n);
for(int i=n-1;i>=0;i--)
{
int in = p[i].first;
int out = p[i].second;
auto iter = lower_bound(p, p+n, make_pair(out,0));
int space, cnt;
if((iter-p) == n)
{
space = in;
cnt = 1;
}
else
{
space = dp[iter - p].first - out + in;
cnt = dp[iter-p].second;
}
if(i<n-1)
{
if(space > dp[i+1].first)
{
space = dp[i+1].first;
cnt = dp[i+1].second;
}
else if(space == dp[i+1].first)
{
cnt = (cnt + dp[i+1].second)%mod;
}
}
dp[i] = make_pair(space, cnt);
}
cout<<dp[0].second<<endl;
}
return 0;
}
