【题解】「SP34013」SEUG - Seetha’s Unique Game

这道题一看就是贪心。

使放的石头少，就需要石头大。

那么就可以将石头重量排序，从大到小。

这道题里面看似东西很多，但是很多东西都是没有用的。比如说：箱子的长和宽，因为题目中说「每加一个石头，水的高度就会增加那个石头的重量那么多。」，根本没有用到长和宽，只需要高度。

其次，添加的石头的总重量要大于（不是大于等于）长方体剩下的高度。所以只需要循环每次添加最重的石头，当：剩下的高度大于石头总重量时，停止循环，输出石头数量。

详细的，看代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define line cout << endl

using namespace std;

int t;

bool cmp(int x, int y) {

	return x > y;

}

int main() {

	cin >> t;

	for (int T = 1; T <= t; T++) {//T组数据

		int a, b, c, d;//分别表示：箱子的长宽高和箱子里有多高的水

		cin >> a >> b >> c >> d;

		int n;

		cin >> n;

		int w[n + 5];

		for (int i = 1; i <= n; i++) {

			cin >> w[i];

		}

		sort(w + 1, w + n + 1, cmp);//把石头的重量从大到小排序

		int ans = 0, cnt = 0;//分别表示：用了的石头的数量，和

		while (c - d >= cnt) {//当剩下的高度还小于等于石头的总重量时，进入循环

			ans++;//用了的石头的数量加一

			cnt += w[ans];//其实这里的ans就是代表用到了第几块石头，不用再建变量，浪费空间（其实是懒得再建变量了（（（

		}

		cout << ans;//输出答案

		line;//换行!!!

        //换行!!!

        //换行!!!

        //重要的事情说三遍（

	}

	return 0;

}

不要抄哦\QAQ，最重要的是自己理解，自己思考。\QAQ

巴特西

【题解】「SP34013」SEUG - Seetha’s Unique Game

最新文章

热门文章