NOIP2019 pj备战计划-5

Task pj试炼场2-6

T1 P1090

贪心里比较基础的了,先把小的合掉,如果和大的后面会操作多次不能做到最优解

优先队列写起来很快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,a,ans;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a;
q.push(a);
}
while(q.size()!=1)
{
int x=q.top();
q.pop();
int y=q.top();
q.pop();
q.push(x+y);
ans+=x+y;
}
cout<<ans<<endl;
}

T2 P1181

不能再简单的红题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1,a,sum;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a;
if(a+sum<=m)sum+=a;
else sum=a,ans++;
}
cout<<ans<<endl;
}

T3 P1208

水题too.

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<bits/stdc++.h>
using namespace std;
int m,n,sum,ans;
struct node
{
int price,num;
}p[1000000];
bool cmp(node a,node b)
{
return a.price<b.price;
}
int main()
{
cin>>m>>n;
for(int i=0;i<n;i++)
cin>>p[i].price>>p[i].num;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
if(sum+p[i].num>m)
{
ans+=p[i].price*(m-sum);
break;
}
else
{
sum+=p[i].num;
ans+=p[i].price*p[i].num;
}
}
cout<<ans<<endl;
}

T4 P1223

和T1类似,小学奥数

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
int num,t;
}p[10005];
int n;
double ans;
bool cmp(node a,node b)
{
if(a.t!=b.t)return a.t<b.t;
return a.num<b.num;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>p[i].t;
p[i].num=i;
}
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
cout<<p[i].num+1<<" ";
ans+=p[i].t*(n-i-1);
}
printf("\n%.2f\n",1.0*ans/n);
}

T5 P1094

凭直觉的贪心吧。。。每次选最大的和最小的,如果不行最大的单独一组,行就配一对

简单证明:在最大的和最小的可以配的前提下,如果最大的和a可行,最小的和b可行(a,b都是另外的数),则互换没有关系;而如果不行,只可能是最大的单独一组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int v,n,a[30005];
int i,j,ans;
int main()
{
cin>>v>>n;
for(int k=0;k<n;k++)cin>>a[k];
sort(a,a+n);
i=0,j=n-1;
while(i<=j)
if(a[i]+a[j]<=v)i++,j--,ans++;
else j--,ans++;
cout<<ans<<endl;
}

T6 P1803

就是以前做过的“今年暑假不AC”,按结束时间排序贪心即可

19行结束战斗QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int n,t,ans;
struct node
{
int beg,end;
}p[1000010];
bool cmp(node a,node b)
{
return a.end<b.end;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>p[i].beg>>p[i].end;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)if(p[i].beg>=t)ans++,t=p[i].end;
cout<<ans<<endl;
}

T7 P1031

重题了唉

T8 P1080

想还是好想的,就是写起来有点烦,还要加高精呃

通过尝试归纳的方式可以知道a*b小的要放前面

由于blog好像不兹瓷latex,所以证明略

那就去做两道高精吧

前置题目1 P1601 高精加

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
#include<bits/stdc++.h>
using namespace std;
string a,b;
string ans;
void add0(string &a,string &b)
{
int x=b.length(),y=a.length();
for(int i=0;i<x-y;i++)
a="0"+a;
}
string add(string a,string b)
{
if(a.length()<b.length())
add0(a,b);
else
add0(b,a);
int len=a.length();
int tmp,tm;
for(int i=len-1;i>=0;i--)
{
tmp=a[i]+b[i]-'0'-'0'+tm;
tm=tmp/10;
tmp%=10;
ans=char(tmp+'0')+ans;
}
if(tm)ans=char(tm+'0')+ans;
return ans;
}
int main()
{
cin>>a>>b;
cout<<add(a,b)<<endl;
}

搞定

前置题目2 P1303 高精乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
string a,b;
int ans[10000000];
void time_(string a,string b)
{
int len1=a.length(),len2=b.length();
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
ans[i+j]+=(a[len1-i-1]-'0')*(b[len2-j-1]-'0'),ans[i+j+1]+=ans[i+j]/10,ans[i+j]%=10;
int len=1000000;
while(ans[len]==0)len--;
if(len<0)cout<<"0"<<endl;
for(int i=len;i>=0;i--)cout<<ans[i];
cout<<endl;
}
int main()
{
cin>>a>>b;
time_(a,b);
}