1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
O(n^2)暴力
int t,n,a[maxn];
bool ok[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
bool mark=false;
scanf("%d",&n);
rep(i,1,n)scanf("%d",&a[i]);
rep(i,2,n-1)
{
int y=a[i],x=-1,z=-1;
for (int j=1;j<i;j++)if (a[j]<y)x=j;
for (int j=i+1;j<=n;j++)if (a[j]<y)z=j;
if (x!=-1&&z!=-1)
{
printf("YESn%d %d %dn",x,i,z);
mark=true;
break;
}
}
if (!mark)printf("NOn");
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
与顺序无关，统计个数即可
int t;
char s[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
int len=strlen(s),shi=0,bu=0,jian=0;
repp(i,0,len)
{
if (s[i]=='R')shi++;
if (s[i]=='P')bu++;
if (s[i]=='S')jian++;
}
if (shi>=bu&&shi>=jian)
{
rep(i,1,len)printf("P");puts("");
}
else if (bu>=shi&&bu>=jian)
{
rep(i,1,len)printf("S");puts("");
}
else
{
rep(i,1,len)printf("R");puts("");
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
贪心思想是逆序遍历
正序遍历可能会造成“浪费”
int t,n,a[maxn],pos,x,minn;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&x);
rep(i,1,n)scanf("%d",&a[i]);
sort(a+1,a+1+n);
int pos=n,ans=0;
while(pos>0)
{
int len=1;
minn=a[pos];
while(minn*len<x)
{
minn=a[--pos];
if (pos<=0)break;
len++;
}
pos--;
if (minn*len>=x)ans++;
if (pos<=0)break;
}
W(ans);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
1.将所有删除了的区间全部找出来
2.对这些区间一一遍历
3.判断性价比如果x/k>y，则尽可能使用第二种操作
但是使用第二种操作需要注意，最后剩下的值一定是该区间的最大值
如果该最大值无法依靠两边比它大的数被删掉，那么就得依靠第一种操作去删除
4.判断性价比如果x/k<=y，则尽可能使用第一种操作
如果区间长度不能整除k，也需要借助第二种操作
这时候同样需要考虑上述情况
int t,n,a[maxn],b[maxn],m,pos[maxn];
ll x,y,k,ans=0;
typedef pair<int,int> P;
vector<P> V;
int main()
{
bool mark=true;
scanf("%d%d",&n,&m);
scanf("%lld%lld%lld",&x,&k,&y);
rep(i,1,n)scanf("%d",&a[i]),pos[a[i]]=i;
a[0]=a[n+1]=-1;
rep(i,1,m)scanf("%d",&b[i]);
if (b[1]!=a[1])V.pb(make_pair(1,pos[b[1]]-1));
if (a[n]!=b[m])V.pb(make_pair(pos[b[m]]+1,n));
rep(i,2,m)
{
int pos1=pos[b[i-1]],pos2=pos[b[i]];
if (pos1>pos2)mark=false;
if (pos1+1==pos2)continue;
V.pb(make_pair(pos1+1,pos2-1));
}
if (!mark)
{
W(-1);
return 0;
}
repp(i,0,V.size())
{
int L=V[i].first,R=V[i].second,len=R-L+1;
int maxx=0;
rep(j,L,R)maxx=max(maxx,a[j]);
if (k*y<x)
{
if (maxx>a[L-1]&&maxx>a[R+1])
{
if (len>=k)ans+=x+(len-k)*y;
else mark=false;
}
else ans+=len*y;
}
else
{
if (len>=k)ans+=x*(len/k)+y*(len%k);
else
{
if (maxx>a[L-1]&&maxx>a[R+1])mark=false;
else ans+=len*y;
}
}
}
if(!mark)W(-1);
else WW(ans);
return 0;
}