pair的排序_贪心_什么时候结束循环_边界情况的考虑_1876_A. Helmets in Night Light

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

int a[N],b[N];

void solve()
{
	int n,p;
	cin>>n>>p;
	
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	
	vector<pair<int,int>> segs(n);
	for(int i=0;i<n;i++)
		segs[i].second=a[i],segs[i].first=b[i];
	
	sort(segs.begin(),segs.end());
	
	LL ans=0;
	LL price=0;
	for(auto e:segs)
		if(e.first<p)
		{
			ans+=e.second;
			ans+=1;
			price+=p;
			price+=(LL)e.first*e.second;
			
			if(ans>=n)
				break;
		}
	if(n>=ans)
		price+=(n-ans)*(LL)p;
	
	if(n==1)
		price=p;
	
	cout<<price<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	while(t--)
		solve();
	
	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

感觉题目做的太少了，pair之类的双关键词的使用不是很熟练

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

int a[N],b[N];

void solve()
{
	int n,p;
	cin>>n>>p;
	
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	
	vector<pair<int,int>> segs(n);
	for(int i=0;i<n;i++)
		segs[i].second=a[i],segs[i].first=b[i];
	
	sort(segs.begin(),segs.end());
	
	LL ans=0;
	LL price=0;
	ans+=1;
	price+=p;
	if(ans<n)
	{
		ans+=segs[0].second;
		price+=segs[0].first*(LL)segs[0].second;
	}
	for(int i=1;i<n;i++)
	{
		if(segs[i].first<p)
		{
			if(ans>=n)
				break;
			ans+=segs[i].second;
			price+=segs[i].first*(LL)segs[i].second;
		}
	}
	if(n>=ans)
		price+=(n-ans)*(LL)p;
	
	cout<<price<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	while(t--)
		solve();
	
	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
64

哭了，改成这样子也过不了，准备看题解了，其实我是写过一个和这个很像的题的，但是那个题暴力可以做

官方题解感觉是把题意解释了一遍，水平太高了，我有点看不懂

看了一份别人提交的代码，感觉自己其实只差临门一脚（？）看似差一点点，其实差一个银河系（狗头）

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

void solve()
{
	int n,p;
	cin>>n>>p;
	
	vector<pair<int,int>> mp(n);
	
	for(int i=0;i<n;i++)
		cin>>mp[i].second;
	for(int i=0;i<n;i++)
		cin>>mp[i].first;
	sort(mp.begin(),mp.end());
	
	int remain=n-1;
	LL ans=p;
	
	for(int i=0;i<n;i++)
	{
		if(remain<=0)
			break;
		
		if(mp[i].second>=remain)
		{
			ans+=min(remain*(LL)p,remain*(LL)mp[i].first);
			break;
		}
		else
		{
			ans+=min((LL)mp[i].second*p,(LL)mp[i].second*mp[i].first);
			remain-=mp[i].second;
		}
	}
	
	cout<<ans<<endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin>>t;
	
	while(t--)
		solve();
	
	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

需要考虑一些细节问题，首先是把两个关键词读进去，因为要按照b排序，所以把b放在第一个关键词的位置，要是不这样，要另外写一个比较函数，重载小于号

然后是首先必须要通知一个居民

所以剩下n-1个居民需要被通知，花费p元，这是不可避免的消耗

然后开始循环，如果所有居民都被通知完了就跳出循环即可

在循环之前要按照第一个关键词排序，因为我们要尽可能地少花钱

如果遍历到的居民可以通知完剩下的所有居民，就更新答案，贪心策略更新答案，然后跳出循环，不够的话，也是更新答案，更新剩余的居民的数目，注意这里有两个整型数的乘法，会超出数据范围，要使用long long

回过头来看也不是很难，主要还是自己要多练