[选择客栈]
题目大意：选择同色调的不同客栈且满足之间至少存在一间客栈的最低消费≤p的方案数
做法：(层层递进嘛）
1：(60)分的做法：直接暴力枚举(i,j)两个客栈判断是不是相同色调的不同客栈，然后从(i)枚举到(j)寻找是不是其中一间客栈的最低消费小于(p)，(ans++,break)
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int n,k,p,ans;
int cnt[55],val[maxn],color[maxn];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++)
scanf("%d%d",&color[i],&val[i]);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
if(color[i] != color[j]) continue;
for(int l=i;l<=j;l++)
{
if(val[l] <= p)
{
ans ++;
break;
}
}
}
printf("%d
",ans);
return 0;
}
但是我发现从(i)枚举到(j)判断是不是有一间客栈的最低消费是不是小于等于(p)，可以用前缀和来优化，(sum[i])表示前i间客栈中满足小于等于(p)的个数，那么(i)到(j)的个数不就是(sum[j]-sum[i-1])吗？只需要判断是不是大于等于1就可以了
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int n,k,p,ans;
int cnt[55],val[maxn],color[maxn];
int sum[maxn];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color[i],&val[i]);
if(val[i] <= p)
sum[i] = sum[i-1] + 1;
else sum[i] = sum[i-1];
}
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
if(color[i] != color[j]) continue;
if(sum[j] - sum[i-1] >= 1) ans ++;
}
printf("%d
",ans);
return 0;
}
但是你会发现还是(60)。。。
2：(80)分的做法：优化了(60)分的暴力：因为判断两个客栈是不是同色调的太浪费时间了，那么我们可以用一个(pos)数组把相同颜色的位置全都记录下来，这样就大大减少了枚举量，然后就会喜提(80)分
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int n,k,p,ans;
int cnt[55],val[maxn],color[maxn];
int sum[maxn],pos[55][maxn];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color[i],&val[i]);
cnt[color[i]] ++;
pos[color[i]][cnt[color[i]]] = i;
if(val[i] <= p)
sum[i] = sum[i-1] + 1;
else sum[i] = sum[i-1];
}
for(int col=0;col<k;col++)
for(int i=1;i<cnt[col];i++)
for(int j=i+1;j<=cnt[col];j++)
{
if(sum[pos[col][j]] - sum[pos[col][i]-1] >= 1)
ans ++;
}
printf("%d
",ans);
return 0;
}
3：(100)分做法：优化了(80)分的做法，考虑枚举两个客栈(i,j)的时候，如果(i)客栈与(j)客栈之间有满足最低消费小于等于(p)的客栈(L)的话，那么(j)后面相同颜色的客栈(c)，一定可以与(i)客栈匹配，因为越往后位置越靠后，那么([i,c])就都会包含这个满足最低消费(leq)(p)的客栈(L)，所以(ans)不用一个一个加，而是可以把(j)客栈之后的所有客栈都加进去。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200005;
int n,k,p,ans;
int cnt[55],val[maxn],color[maxn];
int sum[maxn],pos[55][maxn];
int main()
{
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&color[i],&val[i]);
cnt[color[i]] ++;
pos[color[i]][cnt[color[i]]] = i;
if(val[i] <= p)
sum[i] = sum[i-1] + 1;
else sum[i] = sum[i-1];
}
for(int col=0;col<k;col++)
for(int i=1;i<cnt[col];i++)
for(int j=i+1;j<=cnt[col];j++)
{
if(sum[pos[col][j]] - sum[pos[col][i]-1] >= 1)
{
ans += cnt[col] - j + 1;
break;
}
}
printf("%d
",ans);
return 0;
}