1. 钱包
小苯有n个钱包，其中第i个钱包装了ai元，他每天都会恰好使用一个钱包中的钱去购物，尽可能多地购买 一种单价为k元的物品，
日复一日，直到所有钱包中的钱都分别买不起此物品。 在小苯在开始日复一日地购物前，可以向任意一些钱包中再加入一些钱，但总共加入的钱数不超过m.
现在小苯想知道，如果自己以最优方案向钱包中加钱，那么最多可以购买多少件此物品。
排序贪心或者反悔贪心
int main(int argc, char *argv[]) {
int n,k,m;
cin>>n>>k>>m;
vector<int> nums(n);
int res = 0;
for(int i=0;i<n;i++){
cin>>nums[i];
res += nums[i]/k;
nums[i] = k-(nums[i]%k);
}
sort(nums.begin(),nums.end());
for(int i=0;i<n;i++){
if(m>=nums[i]){
res++;
m-=nums[i];
}
else break;
}
cout<<res;
return 0;
}
2. 操作数组
小红有一个长度为2×n-1的数组，每次可以选择其中n个数，将这n个数取反，小红想知道经过若干次操作之后，所有数组元素之和的最大是多少。
思维题，取反居然取相反数，逆天
int main(int argc, char *argv[]) {
int n;
cin>>n;
vector<int> nums(2*n-1);
for(int i=0;i<2*n-1;i++)
cin>>nums[i];
//首先有奇数个数，容易知道可以对任意偶数个数取反，如果n是奇数，可以对所有数取反
int res = accumulate(nums.begin(),nums.end(),0);
vector<int> fan(n);
int dec = INT_MIN; int inc = INT_MAX;
int cnt = 0;
for(int i=0;i<2*n-1;i++){
fan[i] = (-nums[i])-nums[i];
if(fan[i]>0){
inc = min(inc,fan[i]);
res+=fan[i];
cnt++;//需要取反的个数
}
else dec = max(dec,fan[i]);
}
if(n%2==0&&cnt%2==1)
cout<<max(res-inc,res+dec);
else cout<<res;
cout<<endl;
return 0;
}
3. 奇妙树
小红有一棵n个点的树，其中1号点是根。每个点有一个权值ai。如果满足任意节点的权值大于等于其子节点的权值和，那么这棵树就是一棵奇妙树。
小红每次操作可以选择一个点，将其权值加一。请问小红最少需要多少次操作，才能使这棵树变成一棵奇妙树。
后序遍历
vector<int> e[200005];
long long a[200005];
long long ans = 0;
long long dfs(int u, int fa)
{
long long sum = 0;
for (int v : e[u])
{
if (v == fa)
continue;
sum += dfs(v, u);
}
if (sum > a[u])
{
ans += sum - a[u];
}
return max(sum, a[u]);
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
cout << ans << endl;
}
4. 方块染色
思维模拟题
标签：字节,nums,int,res,08,2024.09,取反,long,sum From： https://www.cnblogs.com/929code/p/18411352