Acwing.第 129 场周赛

比赛地址

A.字符串

题目

思路:

只需要用到reverse()反转函数就可以

代码:

#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s;
	cin>>s;
	reverse(s.begin(),s.end());
	cout<<s<<endl;
	
}
int main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;
}

B.奶牛做题

题目链接

思路:

因为做整套试卷会有额外的加分，所有我们可以先枚举能做多少张试卷(0-n)，我们可以先做用时比较少的，再做用时比较大的，因为分数是相同的

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50;
int a[N];
signed main(){
	int n,k,m;
	cin>>n>>k>>m;

	int ans=0;
	for(int i=1;i<=k;i++){
		cin>>a[i];
		ans+=a[i];
	}

	sort(a+1,a+k+1);

	int res=0;
	
	for(int i=0;i<=n;i++){
		int time=m-i*ans;
		if(time<0){
			break;
		}

		int ans1=i*(k+1);
		
		bool flag=false;
		
		for(int j=1;j<=k;j++){
			for(int l=1;l<=n-i;l++){
				time-=a[j];
				if(time<0){
					flag=true;
					break;
				}
				ans1++;
			}
			if(flag){
				break;

			}
		}
		// cout<<ans1<<endl;
		
		res=max(res,ans1);
	}
	cout<<res<<endl;
	return 0;
}

重新分装

题目

思路：

根据题意，我们知道每个箱子都是相同的，所以分螺丝的过程中螺丝的位置不重要，只需要将总数为a的螺丝分成n堆，每堆为ai个就可以了，每次可以把一堆分成三堆或者两堆。
事实上我们可以反向思考一下，每次分成两堆或者三堆不就是可以理解成每次将两堆或三堆合成一堆吗？
这不就是经典的哈夫曼树吗？

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=2e5+10;
typedef pair<LL,int> PLI;

int a[N];
void solve(){
    int n, m = 3;
    cin >> n;

    priority_queue<PLI, vector<PLI>, greater<PLI> > heap;
    for (int i = 0; i < n; i ++ )
    {
        LL w;
        cin >> w;
        heap.push({w, 0});
    }

    while ((n - 1) % (m - 1))
    {
        heap.push({0ll, 0});
        n ++ ;
    }

    LL res = 0;
    while (heap.size() > 1)
    {
        LL sum = 0;
        int depth = 0;
        for (int i = 0; i < m; i ++ )
        {
            sum += heap.top().first;
            depth = max(depth, heap.top().second);
            heap.pop();
        }
        res += sum;
        heap.push({sum, depth + 1});
    }

    cout << res << endl;

}
signed main(){
    int t=1;
    while(t--){
        solve();
    }
    return 0;

}