书海扬帆的博客

题目传送门

这道题目是一道非常经典的贪心问题。由于n的位数非常多,而且删除操作改变的是每个数位,所以我们非常自然地能想到用字符串来存储n。
接下来我们来思考贪心策略, 首先我思考的是,将字符串中最大的s个数字都删去,但是我发现我是错的。比如36251314这个字符串,要删去2位的话,就不应该删6和4,而应该删6和2。综上所述,我们可以得出本题目的贪心策略:从高位到低位搜索,如果各位数字均递增,则删去最后一个数字,否则删除第一个递减区间的首字符。举个栗子,如果1234567要删除2位的话,我们必定是删除6和7,而3654321如果要删除2位的话,我们则要选择删去6和5.
重复以上过程s次,剩下的数字串便是问题的解了。
这里再谈一下0的问题,由于前导0不能输出(你见过有人把123写成0123或是000123嘛)所以我们再来一个布尔变量flag来记录每一位是否为0.但是这个时候还出现了一个问题,就是这个字符串被删除完了,只剩下一个0怎么办?比如说样例7,10删除1位之后,我们还是必须要输出0的。因此我们再建立一个cnt变量来存储输出的数字的个数。如果个数为0,那么说明整个字符串均为0,此时我们还需要输出一个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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
char n[500];
int s,len;
bool flag;
int main(){
scanf("%s",&n);//读入数据
for(int i=0;i<500;i++) if(n[i]!='\0') len++;//计算字符串长度
cin>>s;//读入数据,我们一共要删除s个字符
for(int i=1;i<=s;i++){
for(int j=0;j<len-1;j++)//从字符串的第一个字符开始查找,len是字符串的长度
if(n[j]>n[j+1]){//如果找到了递减区间
for(int k=j;k<len-1;k++) n[k]=n[k+1];
//那么就删除字符串n的第j个字符,后面字符往前调整。
break;
}
len--;//由于已经删除了一个元素,所以长度-1
}
int cnt;//记录被输出字符的个数
for(int i=0;i<len;i++){
if(n[i]!='0') flag=true;//如果不是0,则说明可以输出,flag=1
if(flag) cout<<n[i],cnt++;//如果可以输出那就输出,同时个数增加1
}
if(cnt==0) cout<<0;//如果啥都没输出,就说明整个字符串都是0,此事我们还要输出一个0
return 0;//愉快地结束了
}

50pts

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
long long n,a1,b1,ans,wealth;
struct node{
long long a,b,w;
}c[10010];
bool cmp(node x,node y){
if(x.a*x.b==y.a*y.b) return 1;
return x.a*x.b>y.a*y.b;
}
int main(){
cin>>n>>a1>>b1;
wealth=a1;
for(long long i=0;i<n;i++) cin>>c[i].a>>c[i].b;
sort(c,c+n,cmp);
for(long long i=n-1;i>0;i--) wealth*=c[i].a;
wealth/=c[0].b;
cout<<wealth<<endl;
return 0;
}

100pts

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
#include<iostream>
using namespace std;
struct a{
int lt,rt;
}a[1001];
int main()
{
int f[1001]={0},fs[1001]={0},k[1001];
int m,n;
cin>>n;
for(int i=0;i<=n;i++){
cin>>a[i].lt>>a[i].rt;
k[i]=a[i].rt*a[i].lt;
}
for (int i=1; i<n; i++) {
for (int j=1; j<=n-i; j++){
if (k[j]>k[j+1])
{
int t=a[j].lt;a[j].lt=a[j+1].lt; a[j+1].lt=t;
t=a[j].rt; a[j].rt=a[j+1].rt; a[j+1].rt=t;
t=k[j];k[j]=k[j+1];k[j+1]=t;
}
}
}
f[0]=a[0].lt;
long double s=0,t=a[0].lt;
int si=0;
for(int i=1;i<=n;i++){
if(t/a[i].rt>s)
{
s=t/a[i].rt;
m=0;
for(int j=999;j>=0;j--){
m=10000*m+f[j];
fs[j]=m/a[i].rt;
m%=a[i].rt;
}
si=i;
}
t*=a[i].lt;
m=0;
for (int j=0;j<=999;j++) {
m+=f[j]*a[i].lt;
f[j]=m%10000;
m/=10000;
}
}
m=0;
for (int j=999; j>=0; j--) {
if (m==1)
{
if (fs[j]<10) cout<<"000";
else if (fs[j]<100) cout<<"00";
else if (fs[j]<1000) cout<<"0";
cout<<fs[j];
}
else if(fs[j]>0){cout<<fs[j];
m=1;
}
}
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:725.9k