2024 暑假友谊赛 1
A.096 - Cooking
对于一个食物要么放入一号烤箱要么放入二号烤箱,类似于一号烤箱取或者不取该食物。
那么对于dp[i][j],表示前i个物品中占用j时间是否成立。那么在成立的情况下,对于二号烤箱所占的时间就是sum-j。
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
int n,m,k;
void sovle(){
cin>>n;
vector<int>a(n);
int sum=0;
for(int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
int dp[n+1][sum+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++){
dp[i][j]=0;
}
}
dp[0][0]=1; //前0个物品占用1号烤箱0分钟
for(int i=0;i<n;i++){
for(int j=0;j<=sum;j++){
if(dp[i][j]){
dp[i+1][j]=1; //相当于不将该物品放入1中
dp[i+1][j+a[i]]=1; //将该物品放入1中
}
}
}
int ans=sum;
for(int i=0;i<=sum;i++){
if(dp[n][i]) ans=min(ans,max(i,sum-i));
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
int t = 1;
//cin>>t;
while (t--){
sovle();
}
return 0;
}
B.C - 2D Plane 2N Points
贪心地对红点按x从大到小排序,蓝点按x从小到大排序。然后枚举a,再枚举b,对于满足条件的b,再去找到最小y值的b。我们担心的是,会不会有b点与当前a配对后会造成其他b点浪费的情况。但实际上红点从大到小,蓝点从小到大排序的情况下,因为枚举第一层a的x会不断减小,第二层枚举的x会不断增大,在u处蓝点x满足条件,后面蓝点的x对于u处后面红点的x也一定满足条件,相当于x被忽略掉了,但是y越靠近红点的y越不会浪费。
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
const int mod = 998244353;
int n,m,k,sum,num;
map<int,int>v;
void sovle(){
cin>>n;
vector<pair<int,int> >a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i].first>>a[i].second;
for(int i=0;i<n;i++) cin>>b[i].first>>b[i].second;
sort(b.begin(),b.end());
sort(a.begin(),a.end(),greater<pair<int,int> >());
for(int i=0;i<n;i++){
int u=-1;
for(int j=0;j<n;j++){
if(v[j]||a[i].first>=b[j].first||a[i].second>=b[j].second) continue;
if(u==-1) u=j;
if(u!=-1&&b[u].second>b[j].second) u=j;
}
if(u!=-1){
v[u]=1;
sum++;
}
}
cout<<sum<<endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
int t = 1;
//cin>>t;
while (t--){
sovle();
}
return 0;
}
要求k个三个数的和的最大和,分治思想先求k个前两个数的最大和,再求出这些数与第三个数的最大和。
#include<bits/stdc++.h>
#define endl '\n'
#define mk make_pair
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5+10;
const int mod = 998244353;
int n,m,k,sum,num;
int x,y,z;
void sovle(){
cin>>x>>y>>z>>k;
vector<int>a(x),b(y),c(z);
for(int i=0;i<x;i++) cin>>a[i];
for(int i=0;i<y;i++) cin>>b[i];
for(int i=0;i<z;i++) cin>>c[i];
sort(a.begin(),a.end(),greater<int>());
sort(b.begin(),b.end(),greater<int>());
sort(c.begin(),c.end(),greater<int>());
int xx=0,yy=0,zz=0;
int aa1=0,bb1=0,cc1=0;
vector<int>aa,bb,cc;
for(int i=0;i<x;i++){
for(int j=0;j<y;j++){
aa.push_back(a[i]+b[j]);
}
}
sort(aa.begin(),aa.end(),greater<int>());
while(aa.size()>k){
aa.pop_back();
}
for(auto ed:aa){
for(int j=0;j<z;j++){
bb.push_back(ed+c[j]);
}
}
sort(bb.begin(),bb.end(),greater<int>());
for(auto ed:bb){
if(aa1==k) return;
aa1++;
cout<<ed<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0),cout.tie(0);
int t = 1;
//cin>>t;
while (t--){
sovle();
}
return 0;
}
原文地址:https://blog.csdn.net/2301_80353190/article/details/140398822
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!