链接
题意:
给定一个区间，枚举该区间所有子区间。加上每个子区间第k大的值。
分析:
比赛的时候想到枚举每个数的两边第k个大于该数的区间，但是不敢写，感觉会超时。不过比赛快结束的时候学长用这种思想写出来了，自己真的是一个垃圾。赛后写了一下，结果超时，还是编码水平太差啊~ ， 后来想到了另一种枚举的方法才过了。
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn =
5*
1e5+
10;
int l[maxn] , r[maxn] , a[maxn];
int main(
int argc ,
char *argv[])
{
int t , n , k , i , j;
scanf(
"%d", &t);
while(t--)
{
long long ans =
0;
scanf(
"%d %d", &n , &k);
for(i=
0; i<n; i++)
scanf(
"%d", &a[i]);
for(i=
0; i<n; i++)
{
int lcnt =
1 , rcnt =
1;
for(j=i+
1; j<n; j++)
{
if(rcnt > k)
break;
if(a[j] > a[i])
{
r[rcnt++] = j - i;
}
}
if(j >= n) r[rcnt] = n - i;
for(j=i-
1; j>=
0; j--)
{
if(lcnt > k)
break;
if(a[j] > a[i])
{
l[lcnt++] = i - j;
}
}
if(j <=
0) l[lcnt] = i +
1;
for(j=
0; j<lcnt; j++)
{
ifa(k-j-
1 >= rcnt)
continue;
int lnum = l[j+
1] - l[j];
int rnum = r[k-j] - r[k-j-
1];
ans += (
long long)a[i] * lnum * rnum;
}
}
printf(
"%lld\n", ans);
}
return 0;
}
TLE代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn =
1*
1e6+
1;
int arr[maxn] , total[
30];
int main()
{
int t , n , k , i , j , ii, cnt , cnt1 , aa;
long long num;
scanf(
"%d", &t);
while(t--)
{
scanf(
"%d %d", &n , &k);
for(i=
1; i<=n; i++)
scanf(
"%d", &arr[i]);
long long ans =
0;
for(i=
1; i<=n; i++)
{
cnt =
0; num =
0; aa =
1;
total[++cnt] = i;
for(j=i+
1; j<=n;)
{
if(cnt == k)
break;
if(arr[j] > arr[i]) total[++cnt] = j;
if(cnt ==
1) aa++;
j++;
}
if(k == cnt)
{
num +=
1;
for(; j<=n; j++)
{
if(arr[j] > arr[i])
{
j -=
1;
break;
}
num +=
1;
}
if(j > n) j--;
for(ii=i-
1; ii>=
1; ii--)
{
if(arr[ii] > arr[i] && cnt ==
0)
break;
if(arr[ii] > arr[i]) j=total[cnt] -
1 , cnt--;
num += (j - total[cnt] +
1);
}
}
else
{
j = n; cnt1 = cnt;
for(ii=i-
1; ii>=
1; ii--)
{
if(k == cnt)
break;
if(arr[ii] > arr[i]) cnt++;
}
if(cnt == k)
{
num += (j-total[cnt1]+
1); ;
j = total[cnt1] -
1; cnt1--;
for(; ii>=
1; ii--)
{
if(arr[ii] > arr[i] && cnt1 ==
0)
break;
if(arr[ii] > arr[i]) j = total[cnt1]-
1 , cnt1--;
if(cnt1 !=
0)
num += (j-total[cnt1]+
1);
else
num += aa;
}
}
}
ans += num * (
long long)arr[i];
}
printf(
"%lld\n", ans);
}
return 0;
}
反思:
反观这两个代码可以发现，超时代码需要考虑的情况过于复杂，我的编码水平估计也捉急，所以超时了。而ac代码需要考虑的情况很少，写起来也简单。一直改代码bug，有时真不如重写一遍，还有不论到什么时候都不能放弃。
