[集训Day5]贪心刷题笔记

Todo

  • 刷完洛谷题单贪心的所有题目QwQ
  • 刷十道 提高+/省选-
  • 刷五道 省选+/NOI-

Todo

  • 刷完洛谷题单贪心的所有题目QwQ
  • 刷十道 提高+/省选-
  • 刷五道 省选+/NOI-

P2240 部分背包问题

最简单的贪心,策略是计算每单位重量的价值vi÷miv_i\div m_i

AC Code

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
#include<bits/stdc++.h>
using namespace std;

struct jelly{
double m,v;
}j[102];

bool cmp(jelly j1,jelly j2){
return (j1.v/j1.m) > (j2.v/j2.m);
}

int main(){
int n,t;
double bag = 0.0;
cin>>n>>t;
for(int i = 0;i < n;i++){
cin>>j[i].m>>j[i].v;
}
sort(j,j+n,cmp);
for(int i = 0;i < n;i++){
if(t-j[i].m >= 0){
bag += j[i].v;
t -= j[i].m;
}else{
bag += double(t)*(j[i].v/j[i].m);
break;
}
}
printf("%.2lf",bag);
return 0;
}

P1223 排队接水

贪心的部分很简单,策略肯定是TiT_i大的放后面防止前面的人等。

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
#include <bits/stdc++.h>
using namespace std;

struct people{
int t,idx;
}p[1002];

bool cmp(people a,people b){
return a.t < b.t;
}

int main(){
int n;
double time = 0;
cin>>n;
for(int i = 1;i <= n;i++){
cin>>p[i].t;
p[i].idx = i;
}
sort(p+1,p+1+n,cmp);
for(int i = 1;i <= n;i++){
cout<<p[i].idx<<" ";
time += (n-i)*p[i].t;
}
printf("\n%.2f",time/n);
return 0;
}

P1803 凌乱的yyy / 线段覆盖

贪心策略:右端点排序,能取就取

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;

struct qwq{
int l,r;
}orz[MAXN];

bool cmp(qwq otz,qwq sto){
return otz.r < sto.r;
}

int main(){
int n,count = 1,endt;
cin>>n;
for(int i = 1;i <= n;i++){
cin>>orz[i].l>>orz[i].r;
}
sort(orz+1,orz+1+n,cmp);
endt = orz[1].r;
for(int i = 2;i <= n;i++){
if(orz[i].l >= endt){
count++;
endt = orz[i].r;
}
}
cout<<count;
return 0;
}

P3817 小A的糖果

贪心策略:遍历一次,要吃就吃

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>
#define MAXN 100005
using namespace std;

long long n, x, ans;
long long caddy[MAXN];
int main()
{
cin >> n >> x;
for (long long i = 1; i <= n; i++)
{
cin >> caddy[i];
if (caddy[i] + caddy[i - 1] > x)
{
ans += caddy[i] + caddy[i - 1] - x;
caddy[i] -= caddy[i] + caddy[i - 1] - x;
}
}
cout << ans;
return 0;
}

P1106 删数问题

贪心策略: 保证每一位最优

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
#define MAXN 100005 
using namespace std;

int main(){
string num;
int l,start = 0,min,flag = 1;
cin>>num>>l;

while(l){
min = start;
for(int i = start+1;i <= start+l;i++)
if(num[i] < num[min]) min = i;
l -= (min - start);
start = min+1;
if(num[min] != '0'){
cout<<num[min];
flag = 0;
}
}

while(num[start] != '\0'){
cout<<num[start++];
flag = 0;
}

if(flag) cout<<0;
return 0;
}

P1478 陶陶摘苹果(升级版)

贪心策略:排除摘不到的,然后从用力气小的开始摘

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;

struct qwq{
int x,y;
}orz[5005];

bool cmp(qwq otz,qwq sto){
return otz.y < sto.y;
}

int main() {
int n,s,a,b,ans = 0;
cin>>n>>s>>a>>b;
for (int i = 0; i < n; i++){
cin>>orz[i].x>>orz[i].y;
if(orz[i].x>(a+b)){
i--;n--;
}
}

sort(orz,orz+n,cmp);
for(int i = 0;i < n;i++){
if((s - orz[i].y) >= 0)
ans++;
else
break;
s -= orz[i].y;
}
cout<<ans<<endl;
return 0;
}

P5019 铺设道路

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main(){
int n,d[100005] = {0},ans = 0;
cin>>n;
for (int i = 1; i <= n; i++){
cin>>d[i];
if(d[i] > d[i-1]) ans += (d[i]-d[i-1]);
}
cout<<ans;
return 0;
}
文章作者: Tim
文章链接: http://itstim.xyz/%E9%9B%86%E8%AE%ADDay5-%E8%B4%AA%E5%BF%83%E5%88%B7%E9%A2%98%E7%AC%94%E8%AE%B0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏