VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 1033|回复: 4

[已解决]时间超限,求一更好的算法或者思路

[复制链接]
36_avatar_middle
最佳答案
0 
在线会员 发表于 2021-1-5 18:59:29 | 显示全部楼层 |阅读模式
#include <cstdio>

using namespace std;

int chart[2][300000];

int main()
{
    int n, q, oper, i, j, a, b, k;
    long long sum;
    scanf("%d%d", &n, &q);
    int  temp;
    for (int i = 0; i < n; i++)        //赋初值
    {
        chart[0][i] = i;    //记行坐标
        chart[1][i] = i;        //记列坐标
    }
    while (q--)
    {
        scanf("%d",&oper);
        //求和
        if (oper == 3)
        {
            sum = 0;
            scanf("%d%d%d%d",&i,&a,&j,&b);
            sum=(i*n+a+j*n+b)/2*(j-i+1)*(b-a+1);        //原来位置未变化的和
            for(int x=i;x<=j;x++)                       //减去更改以后行的变化
            {
                if(chart[0][x]<i||chart[0][x]>j)
                    sum+=(j-i+1)*(chart[0][x]-x)*n;
            }
            for(int y=a;y<=b;y++)               //减去更改以后列的变化
            {
                if(chart[1][y]<a||chart[1][y]>b)
                    sum+=(b-a+1)*(chart[1][y]-y);
            }
            printf("%d\n",sum);
        }
        else if (oper == 1)
        {
            scanf("%d%d",&i,&j);
            temp = chart[0][i];
            chart[0][i] = chart[0][j];
            chart[0][j] = temp;

        }
        else if (oper == 2)
        {
            scanf("%d%d",&a,&b);
            temp = chart[1][a];
            chart[1][a] = chart[1][b];
            chart[1][b] = temp;

        }
    }

    return 0;
}
以上为自己编写的代码,但在oj上时间超限,以无思路,求助
最佳答案
83_avatar_small
2021-1-7 14:46:52
本帖最后由 黯魂夜 于 2021-1-7 14:48 编辑

#include"vector"
#include <iostream>
//#include <numeric>
using namespace std;
int main()
{
        int n, q, op, i, j, a, b, x1, x2, y1, y2;                //对应题目的各个变量
        cin >> n >> q;                                        // n 是矩阵的规模  q是操作符数量
        vector<vector<int>>vec;                        //vector容器,自动扩展空间,存放矩阵,因为是n*n,所以要嵌套一个vector在里面
        vector<int>small_vec;                       
        int temp, sum = 0;                                //temp 做行或列交换时临时存放vector中的值
        vector<int>v_sum;                                //v_sum 存放每次求和后的结果

        //初始化矩阵
        for (int k = 0; k < n; k++)
        {
                for (int p = 0; p < n; p++)
                {
                        small_vec.push_back(k*n + p);
                }
                vec.push_back(small_vec);
                small_vec.clear();
        }

        //
        while (q)
        {
                cin >> op;
                // 根据输入的操作符进行操作
                switch (op)
                {
                case 1:
                        cin >> i >> j;
                        for (int k = 0; k < n; k++)
                        {
                                temp = vec[k];
                                vec[k] = vec[j][k];                        //行交换
                                vec[j][k] = temp;
                        }
                        break;
                case 2:
                        cin >> a >> b;
                        for (int k = 0; k < n; k++)
                        {
                                temp = vec[k][a];
                                vec[k][a] = vec[k];                //列交换
                                vec[k] = temp;
                        }
                        break;
                case 3:
                        sum = 0;                //每次累加前sum清0
                        cin >> x1 >> y1 >> x2 >> y2;
                        for (int k = x1; k <= x2; k++)
                        {       
                                for (int p = y1; p <= y2; p++)
                                {
                                        sum += vec[k][p];                //累加
                                }
                        }
                        v_sum.push_back(sum);                //存放每次累加的sum
                        break;
                default:
                        break;
                }
                q--;        //操作符--
        }
        for (auto k : v_sum)
        {
                cout << k << endl;               
        }
        system("pause");        //控制台测试添加的暂停,可注释掉
        return 0;
}
迷惑.png




上一篇:双管道问题求高手解答
下一篇:求解,关于负数补码、原码之间的转换问题
83_avatar_middle
最佳答案
1 
在线会员 发表于 2021-1-7 14:46:52 | 显示全部楼层    本楼为最佳答案   
bestAnswer
本帖最后由 黯魂夜 于 2021-1-7 14:48 编辑

#include"vector"
#include <iostream>
//#include <numeric>
using namespace std;
int main()
{
        int n, q, op, i, j, a, b, x1, x2, y1, y2;                //对应题目的各个变量
        cin >> n >> q;                                        // n 是矩阵的规模  q是操作符数量
        vector<vector<int>>vec;                        //vector容器,自动扩展空间,存放矩阵,因为是n*n,所以要嵌套一个vector在里面
        vector<int>small_vec;                       
        int temp, sum = 0;                                //temp 做行或列交换时临时存放vector中的值
        vector<int>v_sum;                                //v_sum 存放每次求和后的结果

        //初始化矩阵
        for (int k = 0; k < n; k++)
        {
                for (int p = 0; p < n; p++)
                {
                        small_vec.push_back(k*n + p);
                }
                vec.push_back(small_vec);
                small_vec.clear();
        }

        //
        while (q)
        {
                cin >> op;
                // 根据输入的操作符进行操作
                switch (op)
                {
                case 1:
                        cin >> i >> j;
                        for (int k = 0; k < n; k++)
                        {
                                temp = vec[k];
                                vec[k] = vec[j][k];                        //行交换
                                vec[j][k] = temp;
                        }
                        break;
                case 2:
                        cin >> a >> b;
                        for (int k = 0; k < n; k++)
                        {
                                temp = vec[k][a];
                                vec[k][a] = vec[k];                //列交换
                                vec[k] = temp;
                        }
                        break;
                case 3:
                        sum = 0;                //每次累加前sum清0
                        cin >> x1 >> y1 >> x2 >> y2;
                        for (int k = x1; k <= x2; k++)
                        {       
                                for (int p = y1; p <= y2; p++)
                                {
                                        sum += vec[k][p];                //累加
                                }
                        }
                        v_sum.push_back(sum);                //存放每次累加的sum
                        break;
                default:
                        break;
                }
                q--;        //操作符--
        }
        for (auto k : v_sum)
        {
                cout << k << endl;               
        }
        system("pause");        //控制台测试添加的暂停,可注释掉
        return 0;
}
97_avatar_middle
最佳答案
0 
在线会员 发表于 2021-1-7 17:58:35 | 显示全部楼层
有点难度啊
36_avatar_middle
最佳答案
0 
ico_lz  楼主| 发表于 2021-1-8 16:42:21 | 显示全部楼层
黯魂夜 发表于 2021-1-7 14:46
#include"vector"
#include
//#include

内存超限,不过谢谢了,我想我知道了为什么我时间超限,有思路了
83_avatar_middle
最佳答案
1 
在线会员 发表于 2021-1-9 15:50:19 | 显示全部楼层
本帖最后由 黯魂夜 于 2021-1-9 15:51 编辑
焚琴煮鹤 发表于 2021-1-8 16:42
内存超限,不过谢谢了,我想我知道了为什么我时间超限,有思路了


不客气,加油~时间超限,求一更好的算法或者思路
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号-4 )|网站地图wx_jqr

GMT+8, 2023-5-29 23:35

Powered by CcTry.CoM

© 2009-2021 cctry.com

快速回复 返回顶部 返回列表