10 条题解

  • 13
    @ 2022-5-1 22:37:46 
    #include <bits/stdc++.h>
using namespace std;
//贪心思路：尽量选择k[i]最小的（k[i]解释见下）

int main()
{
    int n,m,a[105],k[105],ans,p;
    //n和m是题目中的，a存储每个州人数
    //k存储如果这个州要支持小明的话，此州至少需要多少人支持小明
    //ans是最终输出的答案，p是小明至少要赢得多少州的支持才能当选总统

    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> m;
        for(int j = 1;j <= m;j++)
        {
            cin >> a[j];//输入

            //求出k[i]的值，方便排序
            k[j] = a[j] / 2 + 1;
        }

        //求出p的值
        p = m / 2 + 1;
        ans = 0;

        //排序
        sort(k + 1,k + m + 1);//这里只有前p位是有用的,但全部都要排序
        //不要问我为什么

        //求ans
        for(int j = 1;j <= p;j++)
        {
            ans += k[j];
        }

        //输出
        cout << ans << endl;
    }
    return 0;
}
    • @ 2022-5-1 23:19:58

      第一次写题解，请各位大佬指点指点，谢谢谢谢谢谢

    • @ 2022-5-6 22:32:35

      棒~

    • @ 2022-7-1 18:30:19

      @ 建议加上代码时间复杂度，或者加上思路（我不是大佬qwq）

    • @ 2023-5-11 21:17:31

      厉害

    • @ 2023-11-5 10:37:49

      @ O(5+n*m+p), O(nm)

  • 6
    @ 2022-7-2 17:55:48

    桶排最快！

    桶排序（Bucket Sort），一种排序方法，简单来说就是把数放进对应的桶里，再按桶编号顺序取出，就可以发现，取出的数是有序的。这就是桶排。

    桶排就是经典的空间换时间，它会比 <algorithm> 里的 sort 快。下面给出一段桶排实现代码。

    例：

    #include <cstdio> // printf
#include <iostream> // max
using namespace std;

int n; //数的个数 
int tong[60]; //数组大小至少要排序数的最大值 
int maxn = -0x7ffffff; //排序数的最大值，分别输出 

int main(void){
	scanf("%d" , &n);
	for(int i = 0;i < n;i++){
		int t;
		scanf("%d" , &t);
		tong[t]++; //tong[i] 表示第i个桶存的排序数的个数 
		maxn = max(maxn , t); //更新最大排序数 
	}
	for(int i = 0;i <= maxn;i++)
		if(tong[i]) // 判断tong[i]是否有排序数 
			printf("%d " , i); //输出 
}

    输入：

    5
23 48 51 0 16

    输出：

    0 16 23 48 51

    知道了桶排序，我们即可愉快地写出 AC 代码。

    AC 代码( 4ms )：

    //这次就不加思路了，想必大家应该都会
#include <cstdio>
#include <cstring>
using namespace std;

int n , m;
int tong[60] , ans , l;

int main(void){
	scanf("%d", &n);
	while(n--){
		memset(tong , 0 , sizeof(tong));
		ans = 0;
		l = 0;
		scanf("%d" , &m);
		for(int i = 0;i < m;i++){
			int t;
			scanf("%d" , &t);
			tong[(t >> 1) + 1]++;
		}
		for(int i = 1;i <= 55 && l < (m >> 1) + 1;i++){
			if(tong[i]){
				if(l + tong[i] >= (m >> 1) + 1)
					ans += i * ((m >> 1) + 1 - l);
				else
					ans += i * tong[i];
				l += tong[i];
			}
		}
		printf("%d\n" , ans);
	}
}

    STL：没错，我无处不在~

    STL 中的 优先队列（priority_queue）可以使我们不用排序，什么快排，什么桶排都不需要，你只需加入数据，输出即可。

    事先，你要导入头文件 #include <queue>，这个头文件里包含着 priority_queue（优先队列）。让我们来稍微了解一下priority_queue吧！

    例：

    #include <iostream> //cin
#include <queue> //优先队列（STL）
using namespace std;

int n;
priority_queue <int , vector <int> , greater <int> > q; //优先队列

int main(void){
	cin >> n; //输入
	for(int i = 0;i < n;i++){
		int a;
		cin >> a;
		q.push(a); //加入优先队列中
	}
	for(int i = 0;i < n;i++){
		cout << q.top() << " "; //取末尾
		q.pop(); //弹出
	}
}

    输入：

    5
23 48 51 0 16

    输出：

    0 16 23 48 51

    AC 代码( 10ms )：

    #include <cstdio>
#include <queue>
using namespace std;

int n , m;

int main(void){
	scanf("%d", &n);
	while(n--){
		int ans = 0;
		priority_queue <int , vector <int> , greater <int> > q; //优先队列
		scanf("%d" , &m);
		for(int i = 0;i < m;i++){
			int t;
			scanf("%d" , &t);
			q.push(t); //加入
		}
		for(int i = 0;i < (m >> 1) + 1;i++){
			ans += (q.top() >> 1) + 1;
			q.pop(); //弹出
		}
		printf("%d\n" , ans);
	}
}
    • 3
      @ 2024-1-7 9:23:42

      基础版：

      #include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int m, a[1005], sum = 0;
        cin >> m;
        for (int i = 1; i <= m; i++)
            cin >> a[i];
        sort (a + 1, a + m + 1);
        m /= 2;
        m++;
        for (int i = 1; i <= m; i++)
            sum += a[i] / 2 + 1;
        cout << sum << endl;
    }
    return 0;
}

      稍微加强以下（前缀和）：

      #include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int m, a[1005], sum[1005];
        cin >> m;
        for (int i = 1; i <= m; i++)
            cin >> a[i];
        sort (a + 1, a + m + 1);
        for (int i = 1; i <= m; i++)
            sum[i] = sum[i - 1] + (a[i] / 2 + 1);
        cout << sum[m / 2 + 1] << endl;
    }
    return 0;
}

      当然，我也可以用优先队列水一波：

      #include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int m, sum = 0;
        priority_queue<int, vector<int>, greater<int> > que;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            int x;
            cin >> x;
            que.push(x);
        }
        for (int i = 1; i <= m / 2 + 1; i++)
        {
            sum += que.top() / 2 + 1;
            que.pop();
        }
        cout << sum << endl;
    }
    return 0;
}

      再来发vector：

      #include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        int m, sum = 0;
        vector<int> vec;
        cin >> m;
        for (int i = 1; i <= m; i++)
        {
            int x;
            cin >> x;
            vec.push_back(x);
        }
        sort(vec.begin(), vec.end());
        for (int i = 1; i <= m / 2 + 1; i++)
            sum += vec[i - 1]/ 2 + 1;
        cout << sum << endl;
    }
    return 0;
}
      • 2
        @ 2024-5-13 19:32:39

        这是题目:

        image

        这是根据image内容的改写:

        桶排最快!

        桶排序(Bucket Sort),一种排序方法,简单来说就是把数放进对应的桶里,再按桶编号顺序取出,就可以发现,取出的数是有序的。这就是桶排。

        桶排就是经典的空间换时间，它会比

        <algorithm>

        里的 sort 快。下面给出一段桶排实现代码。

        例:

        #include<cstdio>//printf
#include<iostream>//max
using namespace std;
int n;//数的个数 
int tong[60];//数组大小至少要排序数的最大值 
int maxn=-0x7ffffff;//排序数的最大值,分别输出 
int main(void){
scanf("%d",&n);
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
tong[t]++;//tong[i]表示第i个桶存的排序数的个数 
maxn=max(maxn,t);//更新最大排序数 
}for(int i=0;i<=maxn;i++)
if(tong[i])//判断tong[i]是否有排序数 
printf("%d ",i);//输出 
return 0;
}

        输入:

        5
23 48 51 0 16

        输出:

        0 16 23 48 51

        知道了桶排序,我们即可愉快地写出AC代码。

        这是TA的AC代码(4ms):

        //这次就不加思路了,想必大家应该都会
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int tong[60],ans,l;
int main(void){
scanf("%d",&n);
while(n--){
memset(tong,0,sizeof(tong));
ans=0;
l=0;
scanf("%d",&m);
for(int i=0;i<m;i++){
int t;
scanf("%d",&t);
tong[(t>>1)+1]++;
}for(int i=1;i<=55&&l<(m>>1)+1;i++){
if(tong[i]){
if(l+tong[i]>=(m>>1)+1)
ans+=i*((m>>1)+1-l);
else
ans+=i*tong[i];
l+=tong[i];
}}printf("%d\n",ans);
}return 0;
}

        STL:没错,我无处不在~

        STL中的优先队列(priority_queue)可以使我们不用排序,什么快排,什么桶排都不需要,你只需加入数据,输出即可。

        事先,你要导入头文件

        #include<queue>

        ,这个头文件里包含着priority_queue(优先队列)。让我们来稍微了解一下priority_queue吧!

        例:

        #include<iostream>//cin
#include<queue>//优先队列(STL)
using namespace std;
int n;
priority_queue <int,vector<int>,greater<int>>q;//优先队列
int main(void){
cin>>n; //输入
for(int i=0;i<n;i++){
int a;
cin>>a;
q.push(a);//加入优先队列中
}for(int i=0;i<n;i++){
cout<<q.top()<<" ";//取末尾q.pop();//弹出
}return 0;
}

        输入:

        5
23 48 51 0 16

        输出:

        0 16 23 48 51

        这是TA的AC代码(10ms):

        #include<cstdio>
#include<queue>
using namespace std;
int n,m;
int main(void){
scanf("%d",&n);
while(n--){
int ans=0;
priority_queue<int,vector<int>,greater<int>>q;//优先队列scanf("%d",&m);
for(int i=0;i<m;i++){ 
int t;
scanf("%d",&t);
q.push(t);//加入
}for(int i=0;i<(m>>1)+1;i++){
ans+=(q.top()>>1)+1;
q.pop();//弹出
}printf("%d\n" , ans);
}return 0;
}

        这是我的代码:

        image

        麻烦点一下image呗。

        • 2
          @ 2023-8-21 13:26:33

          枚举 带那么一点点的贪心

          #include <iostream>
#include <algorithm>
using namespace std;
int n,m,sum,a[105];
int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        sum=0;// 别忘了初始化！！！
        cin >> m;
        for (int i=1;i<=m;i++)
        {
            cin >> a[i];
        }
        sort(a+1,a+m+1);
        for (int i=1;i<=(m/2+1);i++)
        {
            sum+=(a[i]/2+1);
        }
        cout << sum << endl;
    }
    return 0;
}
          • 0
            @ 2024-3-31 19:30:01 
            #include<bits/stdc++.h>
using namespace std;
int b[105];
int main(){
    int n,m,a[105];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        for(int j=1;j<=m;j++){
            cin>>a[j];
        }
        sort(a+1,a+1+m);
        for(int j=1;j<=m/2+1;j++){
            b[i]+=a[j]/2+1;
        }
    }
    for(int i=1;i<=n;i++){
    	cout<<b[i]<<endl;
	}
    return 0;
}

            已AC

            刚开始运气好，样例过了，评测一个没过😁（第14行"a[j]"被弄成了"a[i]",第12行，"m"写成了"n"）

            • 0
              @ 2022-9-7 20:32:27 
              #include <bits/stdc++.h>
using namespace std;
int b[105];
int main()
{
    int n,m,a[105];
    cin>> n;
    for(int i = 1;i<=n;i++)
    {
        cin >> m;
        int k = m/2+1;
        for(int j = 1;j<=m;j++)cin >> a[j];
        sort(a+1,a+m+1);
        for(int j = 1;j<=k;j++)b[i]+=a[j]/2+1;
        cout<<b[i]<<endl;
    }
}
//就很简单的思路啦
              </span>
              • -1
                @ 2022-8-22 9:30:15 
                sort(a+1,a+m+1);
sum=0;
for (int j=1;j<=m/2+1;j++)
{
    sum+=a[j]/2+1;
}
cout<<sum<<'\n';
                • -2
                  @ 2023-6-10 12:47:01 
                  #include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[105],k[105],ans,p;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> m;
        for(int j = 1;j <= m;j++)
        {
            cin >> a[j];
            k[j] = a[j] / 2 + 1;
        }
        p = m / 2 + 1;
        ans = 0;
        sort(k + 1,k + m + 1);
        for(int j = 1;j <= p;j++)ans += k[j];
        cout << ans << endl;
    }
    return 0;
}
                • -2
                  @ 2022-4-24 16:12:18

                  鼓励大家写题解，但注意题解格式。

                  给代码两端加上这个会舒服一些

                  ```cpp

                  你的代码

                  ```

                  </span>

                  这个点在键盘的左上角tab上面那个键，注意切换输入法

                  #include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

                  请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

                  抄袭题解一经发现直接取消成绩。

                • 1

                【入门】当总统

                信息

                ID
                1088
                时间
                1000ms
                内存
                32MiB
                难度
                4
                标签
                递交数
                612
                已通过
                283
                上传者
                1. 关于
                2. 联系我们
                3. 隐私
                4. 服务条款
                5. 版权申诉
                6. Language
                7. 兼容模式
                8. 主题
                3. Worker 0, 34ms
                4. Powered by Hydro v4.9.24 Community, Modified by hetao